제출 #1124522

#제출 시각아이디문제언어결과실행 시간메모리
1124522NotLinuxSimurgh (IOI17_simurgh)C++20
0 / 100
13 ms3540 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() const int N = 250; int par[N]; void init(){ iota(par , par + N , 0); } int find(int a){ if(par[a] == a)return a; else return par[a] = find(par[a]); } void merge(int a , int b){ par[find(b)] = find(a); } vector<int> find_roads(int n, vector<int> u, vector<int> v) { int m = sz(u); vector < pair < int , int > > bip[m]; for(int banned = 0;banned<n;banned++){ init(); vector < int > r , edges; for(int i = 0;i<m;i++){ if(u[i] != banned and v[i] != banned and find(u[i]) != find(v[i])){ r.push_back(i); merge(u[i] , v[i]); } else if(u[i] == banned or v[i] == banned){ edges.push_back(i); } } for(int i = 0;i<sz(edges)-1;i++){ r.push_back(edges[i]); int result1 = count_common_roads(r); r.pop_back(); r.push_back(edges[i+1]); int result2 = count_common_roads(r); r.pop_back(); bip[edges[i]].push_back({edges[i+1] , result1 != result2}); bip[edges[i+1]].push_back({edges[i] , result1 != result2}); } } int vis[m] = {0}; vector < int > ans[2]; function<void(int,int)> dfs = [&](int node , int color){ if(vis[node])return; vis[node] = 1; ans[color].push_back(node); for(auto itr : bip[node]){ dfs(itr.first , color ^ itr.second); } }; dfs(0,0); if(sz(ans[0]) == n-1)return ans[0]; else if(sz(ans[1]) == n-1)return ans[1]; else assert(false); }
#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...