Submission #440896

#TimeUsernameProblemLanguageResultExecution timeMemory
440896roseanne_pcyConnecting Supertrees (IOI20_supertrees)C++14
96 / 100
246 ms22212 KiB
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <bits/stdc++.h> #include "supertrees.h" using namespace std; typedef pair<int, int> ii; typedef vector<int> vi; typedef long long ll; #define f first #define s second #define pb push_back #define lb lower_bound #define ub upper_bound #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define rsz resize const int md = 1e9+7; const ll inf = 1e18; const int maxn = 1e3+5; template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } vector<int> par; vector<int> subpar; vector< vector<int> > res; vector<int> bucks[maxn]; vector<int> subbucks[maxn]; void init(vector<int> &p) { for(int i = 0; i< (int) p.size(); i++) p[i] = i; } int findset(vector<int> &p, int x) { if(p[x] == x) return x; return p[x] = findset(p, p[x]); } void unionset(vector<int> &p, int x, int y) { int a = findset(p, x); int b = findset(p, y); if(a == b) return; p[a] = b; } void addedge(int u, int v) { res[u][v] = res[v][u] = 1; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); par = vector<int>(n, 0); subpar = vector<int>(n, 0); res.assign(n, vector<int>(n, 0)); init(par); init(subpar); bool good = true; for(int i = 0; i< n; i++) { for(int j = i+1; j< n; j++) { if(p[i][j] > 0) { unionset(par, i, j); } } } for(int i = 0; i< n; i++) { for(int j = i+1; j< n; j++) { if(p[i][j] == 0) { if(findset(par, i) == findset(par, j)) { return 0; } } } } for(int i = 0; i< n; i++) { for(int j = i+1; j< n; j++) { if(p[i][j] == 1) { unionset(subpar, i, j); } } } for(int i = 0; i< n; i++) { for(int j = i+1; j< n; j++) { if(p[i][j] >= 2) { if(findset(subpar, i) == findset(subpar, j)) { return 0; } } } } for(int i = 0; i< n; i++) { if(findset(subpar, i) != i) { addedge(findset(subpar, i), i); } else bucks[findset(par, i)].pb(i); subbucks[findset(subpar, i)].pb(i); } for(int i = 0; i< n; i++) { if((int) bucks[i].size() <= 1) continue; if((int) bucks[i].size() == 2) return 0; int val = -1; for(int j = 0; j< (int) bucks[i].size(); j++) { for(int k = j+1; k< (int) bucks[i].size(); k++) { int u = bucks[i][j], v = bucks[i][k]; for(int su : subbucks[u]) { for(int sj : subbucks[v]) { if(val == -1) val = p[u][v]; else if(val != p[u][v]) return 0; } } } } for(int j = 0; j+1< (int) bucks[i].size(); j++) { addedge(bucks[i][j], bucks[i][j+1]); } addedge(bucks[i][0], bucks[i].back()); if(val == 3 && bucks[i].size() == 3) return 0; if(val == 3) addedge(bucks[i][0], bucks[i][2]); } build(res); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:146:14: warning: unused variable 'sj' [-Wunused-variable]
  146 |      for(int sj : subbucks[v])
      |              ^~
supertrees.cpp:144:13: warning: unused variable 'su' [-Wunused-variable]
  144 |     for(int su : subbucks[u])
      |             ^~
supertrees.cpp:69:7: warning: unused variable 'good' [-Wunused-variable]
   69 |  bool good = true;
      |       ^~~~
#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...