Submission #1113747

#TimeUsernameProblemLanguageResultExecution timeMemory
1113747epicci23Simurgh (IOI17_simurgh)C++17
51 / 100
655 ms3016 KiB
#include "bits/stdc++.h" #include "simurgh.h" //#define int long long #define all(v) v.begin() , v.end() #define sz(a) (int)a.size() using namespace std; const int N = 505; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct DSU{ vector<int> par,siz; stack<array<int,2>> st; DSU(int _n){ siz.assign(_n,1); par.assign(_n,0); iota(all(par),0); } int find(int a){ if(par[a]==a) return a; return find(par[a]); } void unite(int a,int b){ a=find(a),b=find(b); if(a==b) return; if(siz[a]>siz[b]) swap(a,b); st.push({a,b}); par[a]=b; siz[b]+=siz[a]; } void rollback(){ if(st.empty()) return; auto x = st.top(); st.pop(); par[x[0]] = x[0]; siz[x[1]] -= siz[x[0]]; } }; vector<array<int,2>> edges; vector<int> kader; int n,m,tot=0; bool check(int a){ vector<int> vis(m, 0); if(kader[a] == -1) return 0; if(kader[a] == 1) return 1; if(count(all(kader),1) == n - 1) return 0; vector<int> span; DSU dsu(n),dsu2(n); for(int x = 0; x < m ; x++){ if(kader[x] != 1) continue; span.push_back(x); vis[x] = 1; dsu.unite(edges[x][0],edges[x][1]); dsu2.unite(edges[x][0],edges[x][1]); } if(dsu.find(edges[a][0])==dsu.find(edges[a][1])){ kader[a] = -1; return 0; } dsu.unite(edges[a][0],edges[a][1]); int sil = sz(span); vis[a] = 1; span.push_back(a); for(int i = a + 1; i < m ; i++){ if(dsu.find(edges[i][0]) == dsu.find(edges[i][1])) continue; if(kader[i] != 0) continue; dsu.unite(edges[i][0],edges[i][1]); dsu2.unite(edges[i][0],edges[i][1]); vis[i] = 1; span.push_back(i); } int kaydet = count_common_roads(span); span.erase(span.begin()+sil); vector<int> same; same.push_back(a); for(int i = a + 1; i < m ; i++){ if(vis[i]) continue; if(kader[i] != 0) continue; if(dsu2.find(edges[i][0]) == dsu2.find(edges[i][1])) continue; if(sz(same)+tot>=n){ for(int U : same) kader[U] = -1; return 0; } dsu2.unite(edges[i][0],edges[i][1]); span.push_back(i); int kaydet2 = count_common_roads(span); if(kaydet2 == kaydet + 1){ for(int U : same) kader[U] = -1; kader[i] = 1; tot++; return 0; } else if(kaydet2 == kaydet - 1){ for(int U : same) kader[U] = 1; tot += sz(same); kader[i] = -1; return 1; } else same.push_back(i); span.pop_back(); dsu2.rollback(); } for(int U : same) kader[U] = 1; tot += sz(same); return 1; } vector<int> find_roads(int _n, vector<int> u, vector<int> v){ m = sz(u), n = _n; kader.assign(m, 0); for(int i=0;i<m;i++) edges.push_back({u[i],v[i]}); int xd = rng() % 100; for(int i=0;i<m;i++) check(i); vector<int> ans; for(int i=0;i<m;i++) if(kader[i]==1) ans.push_back(i); return ans; }

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:124:7: warning: unused variable 'xd' [-Wunused-variable]
  124 |   int xd = rng() % 100;
      |       ^~
#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...