Submission #780709

#TimeUsernameProblemLanguageResultExecution timeMemory
780709vjudge1Simurgh (IOI17_simurgh)C++17
70 / 100
79 ms8452 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) { 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; } int mat[nmax][nmax]; vector<int> isgood; vector<int> checked; void solvefori(int 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); } int startmn = sz(candr) - 1; copy(all(nv), back_inserter(candr)); for(int i = 1; i <= flag; i++) { //cerr << "--\n"; vector<int> rez; int mx = -1; for(int j = 0; j < sz(atrs[i]); j++) { int u = atrs[i][j]; candr[startmn + i] = u; if(checked[u] && isgood[u]) { mx = ask(candr); break; } } for(int j = 0; j < sz(atrs[i]); j++) { int u = atrs[i][j]; candr[startmn + i] = u; if(!checked[u]) rez.emplace_back(ask(candr)); else rez.emplace_back(-1); } if(mx == -1) mx = *max_element(all(rez)); for(int j = 0; j < sz(atrs[i]); j++) { checked[atrs[i][j]] = 1; if(rez[j] == mx) isgood[atrs[i][j]] = 1; } } } vector<int> S4(int n, vector<int> u, vector<int> v) { for(int i = 0; i < sz(u); i++) { mat[u[i]][v[i]] = i; mat[v[i]][u[i]] = i; g[u[i]].emplace_back(v[i], i); g[v[i]].emplace_back(u[i], i); } //cerr << "yura\n"; solvefori(0); for(int j = 1; j < n; j++) checked[mat[j][0]] = 1; for(int i = 1; i < n; i++) { vector<int> crr; for(int j = 0; j < n; j++) { if(j == i) continue; crr.emplace_back(mat[i][j]); } int totaltf = ask(crr); for(int j = 0; j < i; j++) totaltf -= isgood[mat[i][j]]; for(int smth = 0; smth < totaltf; smth++) { auto trywith = [&](int lim) { vector<int> ntwr; ntwr.emplace_back(mat[0][i]); int expected = isgood[mat[0][i]]; for(int j = 1; j <= lim; j++) { if(j == i) continue; ntwr.emplace_back(mat[i][j]); if(checked[mat[i][j]]) expected += isgood[mat[i][j]]; } for(int j = lim + 1; j < n; j++) { if(j == i) continue; ntwr.emplace_back(mat[0][j]); if(checked[mat[0][j]]) expected += isgood[mat[0][j]]; } return ask(ntwr) - expected; }; int lim = i - 1; for(int i = 9; i >= 0; i--) { if(lim + (1 << i) >= n) continue; if(trywith(lim + (1 << i)) <= 0) lim += (1 << i); } lim++; checked[mat[i][lim]] = 1; isgood[mat[i][lim]] = 1; } for(int j = 0; j < n; j++) { if(j == i) continue; checked[mat[i][j]] = 1; } } vector<int> lst; for(int i = 0; i < sz(isgood); i++) if(isgood[i]) lst.emplace_back(i); return lst; } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { isgood.resize(sz(u)); checked.resize(sz(u)); occ.resize(n); if(n > 240) return S4(n, u, v); 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++) { solvefori(i); } 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...