Submission #780641

#TimeUsernameProblemLanguageResultExecution timeMemory
780641vjudge1Simurgh (IOI17_simurgh)C++17
30 / 100
91 ms3628 KiB
#include <bits/stdc++.h> #include "simurgh.h" #define all(x) (x).begin(),(x).end() using namespace std; //#define ask count_common_roads using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 500; vector<pii> g[nmax]; vector<int> occ; vector<int> candr; int flag; int cnt = 0; int ask(vector<int> r) { cnt++; if(cnt >= 3e4) { assert(false); } return count_common_roads(r); } void dfs(int x) { occ[x] = flag; for(auto [y, ptr] : g[x]) { if(occ[y] != 0) continue; //cerr << x << ' ' << y << '\t' << ptr << '\n'; occ[y] = flag; candr.emplace_back(ptr); dfs(y); } return; } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { occ.resize(n); vector<int> isgood(sz(u), 0); for(int i = 0; i < sz(u); i++) { g[u[i]].emplace_back(v[i], i); g[v[i]].emplace_back(u[i], i); } for(int i = 0; i < n; i++) { fill(all(occ), 0); candr.clear(); occ[i] = -1; vector<vector<int>> atrs; atrs.emplace_back(); vector<int> nv; flag = 0; for(auto [x, ptr] : g[i]) { if(occ[x] == 0) { flag++; dfs(x); nv.emplace_back(ptr); atrs.emplace_back(); atrs.back().emplace_back(ptr); } else atrs[occ[x]].emplace_back(ptr); } //cerr << i <<'\n'; //for(auto x : candr) cerr << x << ' '; //cerr << '\n'; //for(auto x : nv) cerr << x << ' '; //cerr << '\n'; int startmn = sz(candr) - 1; copy(all(nv), back_inserter(candr)); for(int i = 1; i <= flag; i++) { //cerr << "--\n"; vector<int> rez; for(int j = 0; j < sz(atrs[i]); j++) { int u = atrs[i][j]; candr[startmn + i] = u; rez.emplace_back(ask(candr)); } int mx = *max_element(all(rez)); for(int j = 0; j < sz(atrs[i]); j++) { if(rez[j] == mx) isgood[atrs[i][j]] = 1; } //cerr << "--\n"; } //cerr << "=======\n"; } vector<int> lst; for(int i = 0; i < sz(isgood); i++) if(isgood[i]) lst.emplace_back(i); for(auto x : lst) cerr << x << ' '; cerr << '\n'; return lst; } /** Anul asta se da centroid. -- Surse oficiale */
#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...