Submission #612667

#TimeUsernameProblemLanguageResultExecution timeMemory
612667AugustinasJucasSwapping Cities (APIO20_swap)C++14
13 / 100
347 ms41812 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; vector<pair<int, pair<int, int> > > brn; const int dydis = 1e5 + 10; int tevas[dydis]; int kadaNelinija[dydis]; bool neraLinija[dydis] = {}; vector<int> nodes[dydis]; int A[dydis], B[dydis]; int n, m; vector<pair<int, int> > gr[dydis]; void add(int a, int b, int w) { //cout << "brn " << a << " -- " << b << ", w = " << w << endl; gr[a].push_back({b, w}); gr[b].push_back({a, w}); } int fp(int v) { if(tevas[v] == v) return v; return tevas[v] = fp(tevas[v]); } void conn(int a, int b, int t) { int inA = a; int inB = b; a = fp(a); b = fp(b); // //cout << "jungiu " << inA << "(yra_linija = " << !neraLinija[a] <<") su " << inB << "(yra_linija = " << !neraLinija[b] << ")" << endl; if(a == b) { if(neraLinija[a]) return ; neraLinija[a] = true; for(auto x : nodes[a]) kadaNelinija[x] = t; }else { add(inA, inB, t); if(neraLinija[a] || neraLinija[b]) { if(!neraLinija[a]) for(auto x : nodes[a]) kadaNelinija[x] = t; if(!neraLinija[b]) for(auto x : nodes[b]) kadaNelinija[x] = t; } if(nodes[a].size() > nodes[b].size()) swap(a, b); // a ---> b if(!neraLinija[a] && !neraLinija[b]) { set<int> galai = {A[a], B[a], A[b], B[b]}; ////cout << "linju galai: "; for(auto x : galai) //cout << x << " "; // //cout << ", o as jungiu " << inA << " su " << inB << endl; if(galai.count(inA) && galai.count(inB)) { /// sujungiau liniju galus int na, nb; if(A[a] == inA || A[a] == inB) { na = B[a]; }else { na = A[a]; } if(A[b] == inA || A[b] == inB) { nb = B[b]; }else { nb = A[b]; } A[b] = na; B[b] = nb; }else { for(auto x : nodes[a]) kadaNelinija[x] = t; for(auto x : nodes[b]) kadaNelinija[x] = t; neraLinija[b] = true; } } tevas[a] = b; for(auto x : nodes[a]) nodes[b].push_back(x); } } int dbInd = 0; int enter[dydis], leave[dydis]; int rotW[dydis], par[dydis]; int h[dydis]; void dfs(int v, int came) { enter[v] = dbInd++; par[v] = came; // //cout << "esi " << v << endl; for(auto x : gr[v]) { if(x.first == came) continue; h[x.first] = h[v] + 1; rotW[x.first] = x.second; //cout << "rot[" << x.first << "] = " << x.second << ", T./Y., " << rotW[x.first] << endl; dfs(x.first, v); } leave[v] = dbInd++; } const int dd = 10; int lft[dydis][dd]; int mx[dydis][dd]; void calc() { for(int i = 0; i < n; i++) { lft[i][0] = par[i]; //cout << "rotw[" << i << "] = " << rotW[i] << endl; mx[i][0] = rotW[i]; //cout << "mx[" << i << "][" << 0 << "] = " << mx[i][0] << endl; } for(int j = 1; j < dd; j++) { for(int i = 0; i < n; i++) { lft[i][j] = lft[lft[i][j-1]][j-1]; } } for(int j = 1; j < dd; j++) { for(int i = 0; i < n; i++) { mx[i][j] = max(mx[i][j-1], mx[ lft[i][j-1] ][j-1]); //cout << "mx[" << i << "][" << j << "] = " << mx[i][j] << endl; } } } bool isAnc(int a, int b) { return (enter[a] <= enter[b] && leave[b] <= leave[a]); } int lca(int a, int b) { if(isAnc(a, b)) return a; if(isAnc(b, a)) return b; for(int i = dd-1; i > -1; i--) { if(!isAnc(lft[a][i], b)) { a = lft[a][i]; } } return par[a]; } int mxPerBrn(int a, int kek) { int ret = 0; for(int i = dd-1; i > -1; i--) { if((1 << i) <= kek) { ret = max(ret, mx[a][i]); a = lft[a][i]; kek -= (1 << i); } } return ret; } int mxInPath(int a, int b) { int v = lca(a, b); int kair = mxPerBrn(a, h[a] - h[v]); int desn = mxPerBrn(b, h[b] - h[v]); return max(kair, desn); } void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N; m = M; for(int i = 0; i < n; i++) { tevas[i] = i; nodes[i] = {i}; A[i] = i; B[i] = i; neraLinija[i] = false; kadaNelinija[i] = -1; } for(int i = 0; i < m; i++) { brn.push_back({W[i], {U[i], V[i]}}); } sort(brn.begin(), brn.end()); /// nuo maz iki did. for(auto x : brn) { int a = x.second.first; int b = x.second.second; int w = x.first; conn(a, b, w); } h[0] = 0; dfs(0, 0); calc(); for(int i = 0; i < n; i++) { //cout << "virsune nr " << i << " tampa nebe linija, kai w = " << kadaNelinija[i] << endl; } for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { int res = mxInPath(i, j); //cout << "min max val tarp " << i << " ir " << j << " yra " << res << endl; } //cout << endl; } } int getMinimumFuelCapacity(int X, int Y) { if(kadaNelinija[fp(X)] == -1 || kadaNelinija[fp(Y)] == -1) return -1; int ret = mxInPath(X, Y); ret = max(ret, max(kadaNelinija[fp(X)], kadaNelinija[fp(Y)])); return ret; }

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:179:17: warning: unused variable 'res' [-Wunused-variable]
  179 |             int res = mxInPath(i, j);
      |                 ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...