Submission #1076890

#TimeUsernameProblemLanguageResultExecution timeMemory
1076890mariaclaraThousands Islands (IOI22_islands)C++17
18.40 / 100
44 ms14672 KiB
#include "islands.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pb push_back #define mk make_pair #define fr first #define sc second vector<int> ord, vis, valid; vector<vector<pii>> edges, tedges; void dfs(int x) { vis[x] = 1; for(auto [viz,ind] : edges[x]) if(!vis[viz]) dfs(viz); ord.pb(x); } void find_scc(int x) { vis[x] = 1; for(auto [viz, ind] : tedges[x]) { if(!vis[viz]) { valid[x] = valid[viz] = 1; find_scc(viz); } } } vector<int> at, in_ans; vector<int> ciclo(int x, int raiz) { vis[x] = 1; for(auto [viz,ind] : edges[x]) { if(viz == raiz) { at.pb(ind); return at; } if(!vis[viz]) { at.pb(ind); vector<int> v = ciclo(viz, raiz); if(!v.empty()) return v; } } return {}; } variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) { edges.resize(N); tedges.resize(N); vis.resize(N); valid.resize(N); in_ans.resize(M, -1); for(int i = 0; i < M; i++) edges[U[i]].pb({V[i], i}), tedges[V[i]].pb({U[i], i}); //cout << "OK" << endl; for(int i = 0; i < N; i++) if(!vis[i]) dfs(i); reverse(all(ord)); vis.clear(); vis.resize(N); for(auto x : ord) if(!vis[x]) find_scc(x); // agora basta ver se tem como chegar em um no valido de 2 formas vector<vector<pii>> s(N); queue<tuple<int,int,int>> fila; fila.push({0,-1,-1}); while(!fila.empty()) { auto [x, s_e, pai_edge] = fila.front(); fila.pop(); if(sz(s[x]) >= 2) continue; if(sz(s[x]) == 1 and s[x][0].fr == s_e) continue; if(s_e != -1) s[x].pb({s_e, pai_edge}); for(auto [viz, ind] : edges[x]) { if(s_e == -1) fila.push({viz, ind, ind}); else fila.push({viz, s_e, ind}); } } for(int i = 0; i < N; i++) { if(sz(s[i]) >= 2 and valid[i]) { vis.clear(); vis.resize(N); vector<int> c = ciclo(i, i), ans, cam1, cam2; int x1 = 0, x2 = 0, m = sz(c); for(int j = 0; j < m; j++) in_ans[c[j]] = j, c.pb(c[j]); for(int x = i; ; ) { if(s[x][0].fr == s[i][0].fr) cam1.pb(s[x][0].sc), x = U[s[x][0].sc]; else cam1.pb(s[x][1].sc), x = U[s[x][1].sc]; if(in_ans[cam1.back()] != -1) x1 = in_ans[cam1.back()], cam1.clear(); if(x == 0) break; } for(int x = i; ; ) { if(s[x][0].fr == s[i][1].fr) cam2.pb(s[x][0].sc), x = U[s[x][0].sc]; else cam2.pb(s[x][1].sc), x = U[s[x][1].sc]; if(in_ans[cam2.back()] != -1) x2 = in_ans[cam2.back()], cam2.clear(); if(x == 0) break; } for(int j = sz(cam1)-1; j >= 0; j--) ans.pb(cam1[j]); for(int j = x1; j < x1+m; j++) ans.pb(c[j]); for(int j = 0; j < sz(cam1); j++) ans.pb(cam1[j]); for(int j = sz(cam2)-1; j >= 0; j--) ans.pb(cam2[j]); for(int j = x2+m-1; j >= x2; j--) ans.pb(c[j]); for(int j = 0; j < sz(cam2); j++) ans.pb(cam2[j]); return ans; } } return 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...