Submission #551825

#TimeUsernameProblemLanguageResultExecution timeMemory
551825nicolaalexandraSwapping Cities (APIO20_swap)C++14
13 / 100
189 ms29508 KiB
#include <bits/stdc++.h> #include "swap.h" #define DIM 200010 #define INF 2000000000 using namespace std; struct muchie{ int x,y,cost; } mch[DIM]; vector<pair <int,int> > L[DIM]; vector <int> a[DIM]; int t[DIM],ok[DIM],g[DIM],dp[DIM]; int n,m,subtask,maxi; inline int cmp (muchie a, muchie b){ return a.cost < b.cost; } inline int get_rad (int x){ while (t[x] > 0) x = t[x]; return x; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n = N, m = M; for (int i=0;i<m;i++){ int x = U[i], y = V[i], cost = W[i]; x++, y++; L[x].push_back(make_pair(y,cost)); L[y].push_back(make_pair(x,cost)); maxi = max (maxi,cost); mch[i+1] = {x,y,cost}; } subtask = 1; for (int i=1;i<=n;i++) if (L[i].size() > 2) subtask = 0; sort (mch+1,mch+m+1,cmp); for (int i=1;i<=n;i++){ t[i] = dp[i] = -1; ok[i] = g[i] = 0; a[i].push_back(i); } for (int i=1;i<=m;i++){ int x = mch[i].x, y = mch[i].y; int radx = get_rad(x), rady = get_rad(y); if (radx != rady){ if (t[radx] > t[rady]) swap (radx, rady); if (!ok[radx] && ok[rady]){ for (auto it : a[radx]) dp[it] = mch[i].cost; ok[radx] = 1; } if (ok[radx] && !ok[rady]){ for (auto it : a[rady]) dp[it] = mch[i].cost; } for (auto it : a[rady]) a[radx].push_back(it); a[rady].clear(); //ok[radx] |= ok[rady]; t[radx] += t[rady]; t[rady] = radx; g[x]++, g[y]++; if (g[x] >= 3 || g[y] >= 3){ if (!ok[radx]){ ok[radx] = 1; for (auto it : a[radx]) dp[it] = mch[i].cost; } } } else { /// o sa am un ciclu in componenta asta if (!ok[radx]){ ok[radx] = 1; for (auto it : a[radx]) dp[it] = mch[i].cost; } } //if (get_rad(X) == get_rad(Y) && ok[get_rad(X)]) // return mch[i].cost; } } int getMinimumFuelCapacity(int X, int Y) { if (subtask == 1){ if (m == n-1) return -1; else return maxi; } X++, Y++; if (dp[X] == -1 || dp[Y] == -1) return -1; else return max (dp[X],dp[Y]); } /* int main (){ FILE *fin = fopen ("date.in", "r"); FILE *fout = fopen ("date.out", "w"); int N, M; assert(2 == fscanf(fin, "%d %d", &N, &M)); std::vector<int> U(M), V(M), W(M); for (int i = 0; i < M; ++i) { assert(3 == fscanf(fin, "%d %d %d", &U[i], &V[i], &W[i])); } int Q; assert(1 == fscanf(fin,"%d", &Q)); std::vector<int> X(Q), Y(Q); for (int i = 0; i < Q; ++i) { assert(2 == fscanf(fin,"%d %d", &X[i], &Y[i])); } init(N, M, U, V, W); std::vector<int> minimum_fuel_capacities(Q); for (int i = 0; i < Q; ++i) { minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]); } for (int i = 0; i < Q; ++i) { fprintf(fout, "%d\n", minimum_fuel_capacities[i]); } return 0; } */
#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...