Submission #1034243

#TimeUsernameProblemLanguageResultExecution timeMemory
1034243GrayConnecting Supertrees (IOI20_supertrees)C++17
21 / 100
159 ms28248 KiB
#include "supertrees.h" #include <cassert> #include <map> #include <vector> using namespace std; #define ll long long #define ff first #define ss second #define ln "\n" #define pll pair<ll, ll> struct DSU{ vector<int> p; int n, cnt; DSU(int N){ n=N; cnt=n; p.resize(n, -1); } int get(int x){ return p[x]==-1?x:p[x]=get(p[x]); } bool unite(int a, int b){ a=get(a); b=get(b); if (a==b) return 0; cnt--; if (a<b) swap(a, b); p[a]=b; return 1; } }; int construct(std::vector<std::vector<int>> p) { int n = (int)p.size(); DSU tr(n), tr2(n); vector<vector<int>> A(n); for (int i=0; i<n; i++){ for (int j=0; j<n; j++){ if (i!=j and p[i][j]){ tr.unite(i, j); if (p[i][j]==1) tr2.unite(i, j); } } } map<int, vector<int>> ccs; for (int i=0; i<n; i++){ // assert(tr.get(i)<tr.cnt); ccs[tr.get(i)].push_back(i); } vector<vector<int>> ans(n, vector<int>(n)); vector<vector<int>> shadow(n, vector<int>(n)); for (auto &[_, arr]:ccs){ map<int, vector<int>> groups; for (auto ch:arr){ groups[tr2.get(ch)].push_back(ch); } vector<int> circle; for (auto &[icc,mem]:groups){ for (ll j=1; j<(int)mem.size(); j++){ ans[mem[j]][mem[j-1]]=ans[mem[j-1]][mem[j]]=1; } for (ll j=0; j<(int)mem.size(); j++){ for (ll k=j+1; k<(int)mem.size(); k++){ shadow[mem[j]][mem[k]]=shadow[mem[k]][mem[j]]=1; } } circle.push_back(mem[0]); } if (circle.size()==1) continue; for (ll j=0; j<(int)circle.size(); j++){ int nxt = (j+1)%(int)(circle.size()); ans[circle[j]][circle[nxt]]=ans[circle[nxt]][circle[j]]=1; } for (ll j=0; j<(int)(circle.size()); j++){ for (ll k=j+1; k<(int)(circle.size()); k++){ shadow[circle[j]][circle[k]]=shadow[circle[k]][circle[j]]=2; } } } for (ll i=0; i<n; i++){ for (ll j=0; j<n; j++){ if ((i!=j and p[i][j]!=shadow[i][j]) or p[i][j]==3){ return 0; } } } build(ans); return 1; }
#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...