Submission #369783

#TimeUsernameProblemLanguageResultExecution timeMemory
369783CodePlatinaMeetings (JOI19_meetings)C++14
0 / 100
3084 ms620 KiB
#include "meetings.h" #include <vector> #include <algorithm> #include <iostream> #include <unordered_set> //#define DEBUG using namespace std; unordered_set<int> gph[2020]; bool chc[2020]; int sz[2020]; bool rchc[2020]; int cen(int x, int p, int s) { for(auto y : gph[x]) if(y != p && !chc[y] && sz[y] > s) return cen(y, x, s); return x; } void dfs(int x, int p) { sz[x] = 1; for(auto y : gph[p]) if(y != p && !chc[y]) { dfs(y, x); sz[x] += sz[y]; } } void Solve(int N) { for(int i = 1; i < N; ++i) if(!rchc[i]) { rchc[i] = true; for(int j = 0; j < N; ++j) chc[j] = false; int pr = 0; while(1) { dfs(pr, -1); int r = cen(pr, -1, sz[pr] / 2); dfs(r, -1); chc[r] = true; #ifdef DEBUG cout << endl; cout << "i r" << endl; cout << i << ' ' << r << endl; cout << endl; #endif vector<int> chd; for(auto j : gph[r]) if(!chc[j]) chd.push_back(j); sort(chd.begin(), chd.end(), [](int x, int y){ return sz[x] > sz[y]; }); bool flag = true; for(auto c : chd) { int t = Query(r, c, i); if(t != r) { if(t != c) { rchc[t] = true; gph[r].erase(c); gph[c].erase(r); gph[r].insert(t); gph[t].insert(r); gph[c].insert(t); gph[t].insert(c); gph[i].insert(t); gph[t].insert(i); goto A; } pr = c; flag = false; break; } } if(flag) { gph[r].insert(i); gph[i].insert(r); goto A; } } A:; #ifdef DEBUG cout << endl; cout << "gph" << endl; for(int i = 0; i < N; ++i) for(auto j : gph[i]) if(j > i) cout << i << ' ' << j << endl; cout << endl; #endif } for(int i = 0; i < N; ++i) for(auto j : gph[i]) if(j > i) Bridge(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...