Unfortunately we were unable to fully decode your file, as it is not encoded in UTF-8.
You can try to decode it yourself by downloading it here.
/// wykorzystane zadanie komiwoja�er z 9. oi #include <iostream> #include <cstdio> #include <vector> #include <cmath> #include<algorithm> #define maxN 200005 #define maxO 500005 using namespace std; int currTree, Tin[maxN], Tout[maxN], Depth[maxN], D[20][maxN], mxd=0, tim, fiol[maxN], tab[maxN], pary[2][maxN], tree[maxN]; bool vst[maxN]; vector <int> G[maxN]; vector< pair< int, pair<int, int> > > osad; void dfs (int a) { vst[a]=1; tree[a] = currTree; tim++; Tin[a]=tim; for (int i=0; i<G[a].size(); i++) if (Depth [G[a][i]]==0) { Depth [G[a][i]]=Depth[a]+1; mxd=max(mxd, Depth [G[a][i]]); D[0][G[a][i]]=a; dfs(G[a][i]); } Tout[a]=tim; } bool potomek (int a, int b) { return (Tin[a]<=Tin[b] && Tout[a]>=Tout[b]); } bool cmp(pair<int, pair<int, int> > a,pair<int, pair<int, int> > b ){ return (a.first > b.first ); } int LCA (int a, int b) { if (potomek (a,b)) return a; else if (potomek (b, a) ) return b; int i=a, j = mxd; while(j>=0){ if(potomek(b, D[j][i])) j--; else i=D[j][i]; } return D[0][i]; } int main () { int n, m, k; scanf ("%d%d%d", &n, &m, &k); for(int i=1; i<=n; ++i){ scanf("%d", &fiol[i]); tab[i]=i; } for (int i=0; i<m; i++) { int a, b; scanf ("%d%d", &a, &b); pary[0][i] = a; pary[1][i] = b; G[a].push_back(b); G[b].push_back(a); } int wsk=1; for(int i=m-1; i>=0; i--) for(int j=1; j>=0; j--) if(vst[pary[j][i]]==0) { // printf(" - %d \n", pary[j][i] ); currTree = pary[j][i]; Depth[pary[j][i]] = 1; tree[pary[j][i]]=wsk; wsk++; dfs(pary[j][i]); D[0][pary[j][i]]=1; } double o=log2(mxd); mxd=o+1; // printf("%d\n", mxd); for (int p=0; p<=mxd; p++) for (int u=1; u<=n; u++) D[p+1][u] = D[p][D[p][u]]; for(int i=0; i<k; ++i) { int a, b; scanf ("%d%d", &a, &b); osad.push_back(make_pair(Depth[LCA(a, b)], make_pair(a, b))); } sort(osad.begin(), osad.end(), cmp); long long res = 0LL; for(int i=0; i<k; ++i){ int a, b; a = osad[i].second.first; b = osad[i].second.second; if(tree[a] == tree[b]){ int minn = min(fiol[a], fiol[b]); fiol[a] -= minn; fiol[b] -= minn; res += (long long) minn *2; } } printf("%lld", res); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | /// wykorzystane zadanie komiwoja�er z 9. oi #include <iostream> #include <cstdio> #include <vector> #include <cmath> #include<algorithm> #define maxN 200005 #define maxO 500005 using namespace std; int currTree, Tin[maxN], Tout[maxN], Depth[maxN], D[20][maxN], mxd=0, tim, fiol[maxN], tab[maxN], pary[2][maxN], tree[maxN]; bool vst[maxN]; vector <int> G[maxN]; vector< pair< int, pair<int, int> > > osad; void dfs (int a) { vst[a]=1; tree[a] = currTree; tim++; Tin[a]=tim; for (int i=0; i<G[a].size(); i++) if (Depth [G[a][i]]==0) { Depth [G[a][i]]=Depth[a]+1; mxd=max(mxd, Depth [G[a][i]]); D[0][G[a][i]]=a; dfs(G[a][i]); } Tout[a]=tim; } bool potomek (int a, int b) { return (Tin[a]<=Tin[b] && Tout[a]>=Tout[b]); } bool cmp(pair<int, pair<int, int> > a,pair<int, pair<int, int> > b ){ return (a.first > b.first ); } int LCA (int a, int b) { if (potomek (a,b)) return a; else if (potomek (b, a) ) return b; int i=a, j = mxd; while(j>=0){ if(potomek(b, D[j][i])) j--; else i=D[j][i]; } return D[0][i]; } int main () { int n, m, k; scanf ("%d%d%d", &n, &m, &k); for(int i=1; i<=n; ++i){ scanf("%d", &fiol[i]); tab[i]=i; } for (int i=0; i<m; i++) { int a, b; scanf ("%d%d", &a, &b); pary[0][i] = a; pary[1][i] = b; G[a].push_back(b); G[b].push_back(a); } int wsk=1; for(int i=m-1; i>=0; i--) for(int j=1; j>=0; j--) if(vst[pary[j][i]]==0) { // printf(" - %d \n", pary[j][i] ); currTree = pary[j][i]; Depth[pary[j][i]] = 1; tree[pary[j][i]]=wsk; wsk++; dfs(pary[j][i]); D[0][pary[j][i]]=1; } double o=log2(mxd); mxd=o+1; // printf("%d\n", mxd); for (int p=0; p<=mxd; p++) for (int u=1; u<=n; u++) D[p+1][u] = D[p][D[p][u]]; for(int i=0; i<k; ++i) { int a, b; scanf ("%d%d", &a, &b); osad.push_back(make_pair(Depth[LCA(a, b)], make_pair(a, b))); } sort(osad.begin(), osad.end(), cmp); long long res = 0LL; for(int i=0; i<k; ++i){ int a, b; a = osad[i].second.first; b = osad[i].second.second; if(tree[a] == tree[b]){ int minn = min(fiol[a], fiol[b]); fiol[a] -= minn; fiol[b] -= minn; res += (long long) minn *2; } } printf("%lld", res); return 0; } |