| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1077961 | Hanksburger | Radio Towers (IOI22_towers) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
int tin[100005], pre[100005], final[100005], scc[100005], sz[100005], flag[100005], visited[100005], t, cnt, ok, target, firsttime;
vector<int> ss, ans1, ans2, ans3, ans4, ans5, ans11, ans12, ans21, ans22;
vector<int> adj[100005], s, ans, ans3copy;
map<pair<int, int>, int> mp;
void dfs(int u)
{
tin[u]=pre[u]=(++t);
s.push_back(u);
for (int v:adj[u])
{
if (!tin[v])
{
ss.push_back(mp[{u, v}]);
dfs(v);
ss.pop_back();
if (ok)
break;
if (flag[v])
flag[u]=flag[v];
pre[u]=min(pre[u], pre[v]);
}
else if (!final[v])
pre[u]=min(pre[u], tin[v]);
else if (flag[v])
{
ans2=ss;
ans2.push_back(mp[{u, v}]);
ok=1;
break;
}
}
if (ok)
return;
if (pre[u]==tin[u])
{
int okok=(s.back()!=u);
if (okok && !firsttime)
ans1=ss;
cnt++;
while (s.back()!=u)
{
scc[s.back()]=cnt;
if (okok && !firsttime)
flag[s.back()]=cnt;
sz[cnt]++;
s.pop_back();
}
scc[s.back()]=cnt;
if (okok && !firsttime)
flag[s.back()]=cnt;
sz[cnt]++;
s.pop_back();
if (okok && !firsttime)
firsttime=1;
}
final[u]=1;
}
void dfs2(int u)
{
for (int v:adj[u])
{
if (v==target)
{
ans3.push_back(mp[{u, v}]);
ok=1;
break;
}
if (tin[v]<tin[u])
continue;
ans3.push_back(mp[{u, v}]);
dfs2(v);
if (ok)
break;
ans3.pop_back();
}
}
void dfs3(int u)
{
for (int v:adj[u])
{
if (scc[v]==target)
{
ans4.push_back(mp[{u, v}]);
ok=1;
break;
}
if (tin[v]<tin[u])
continue;
ans4.push_back(mp[{u, v}]);
dfs3(v);
if (ok)
break;
ans4.pop_back();
}
}
void dfs4(int u)
{
visited[u]=1;
for (int v:adj[u])
{
if (visited[v])
continue;
int ind=lower_bound(ans3copy.begin(), ans3copy.end(), v)-ans3copy.begin();
if (ind!=ans3copy.size() && ans3copy[ind]==v)
{
ans5.push_back(mp[{u, v}]);
ok=1;
break;
}
ans5.push_back(mp[{u, v}]);
dfs4(v);
if (ok)
break;
ans5.pop_back();
}
}
variant<bool, vector<int> > find_journey(int n, int m, vector<int> u, vector<int> v)
{
for (int i=0; i<m; i++)
{
adj[u[i]].push_back(v[i]);
mp[{u[i], v[i]}]=i;
}
dfs(0);
if (ok)
{
/*cout << "ans1: ";
for (int i=0; i<ans1.size(); i++)
cout << ans1[i].first << ' ' << ans1[i].second << ' ';
cout << '\n';
cout << "ans2: ";
for (int i=0; i<ans2.size(); i++)
cout << ans2[i].first << ' ' << ans2[i].second << ' ';
cout << '\n';*/
int ind=0;
while (ind<min(ans1.size(), ans2.size()) && ans1[ind]==ans2[ind])
ind++;
for (int i=0; i<ans1.size(); i++)
ans.push_back(ans1[i]);
target=(ans1.empty()?0:v[ans1.back()]);
ok=0;
dfs2(target);
/*cout << "ans3: ";
for (int i=0; i<ans3.size(); i++)
cout << ans3[i].first << ' ' << ans3[i].second << ' ';
cout << '\n';*/
for (int i=0; i<ans3.size(); i++)
ans.push_back(ans3[i]);
int sz1=ans1.size();
for (int i=sz1-1; i>=ind; i--)
ans.push_back(ans1[i]);
for (int i=ind; i<ans2.size(); i++)
ans.push_back(ans2[i]);
int tmp=(ans2.empty()?0:v[ans2.back()]);
for (int i=0; i<ans3.size(); i++)
ans3copy.push_back(u[ans3[i]]);
ans3copy.push_back(v[ans3.back()]);
sort(ans3copy.begin(), ans3copy.end());
ok=0;
ind=lower_bound(ans3copy.begin(), ans3copy.end(), tmp)-ans3copy.begin();
if (ind==ans3copy.size() || ans3copy[ind]!=tmp)
dfs4(tmp);
int sz5=ans5.size();
for (int i=0; i<ans5.size(); i++)
ans.push_back(ans5[i]);
tmp=(ans5.empty()?tmp:v[ans5.back()]);
for (int i=0; i<ans3.size(); i++)
{
if (v[ans3[i]]==tmp)
{
ind=i;
break;
}
}
int sz3=ans3.size();
for (int i=ind; i>=0; i--)
ans.push_back(ans3[i]);
for (int i=sz3-1; i>ind; i--)
ans.push_back(ans3[i]);
for (int i=sz5-1; i>=0; i--)
ans.push_back(ans5[i]);
int sz2=ans2.size();
for (int i=sz2-1; i>=0; i--)
ans.push_back(ans2[i]);
return ans;
}
for (int i=0; i<n; i++)
flag[i]=0;
int scc1=0, scc2=0;
for (int i=1; i<=cnt; i++)
{
if (sz[i]>=2)
{
if (!scc1)
scc1=i;
else if (!scc2)
{
scc2=i;
break;
}
}
}
if (!scc2)
return (bool)0;
target=scc1;
ok=0;
dfs3(0);
ans11=ans4;
ans4.clear();
target=scc2;
ok=0;
dfs3(0);
ans21=ans4;
ans4.clear();
target=(ans11.empty()?0:v[ans11.back()]);
ok=0;
dfs2(target);
ans12=ans3;
ans3.clear();
target=(ans21.empty()?0:v[ans21.back()]);
ok=0;
dfs2(target);
ans22=ans3;
/*cout << "----------11:\n";
for (int i=0; i<ans11.size(); i++)
cout << u[ans11[i]] << ' ' << v[ans11[i]] << '\n';
cout << "----------12:\n";
for (int i=0; i<ans12.size(); i++)
cout << u[ans12[i]] << ' ' << v[ans12[i]] << '\n';
cout << "----------21:\n";
for (int i=0; i<ans21.size(); i++)
cout << u[ans21[i]] << ' ' << v[ans21[i]] << '\n';
cout << "----------22:\n";
for (int i=0; i<ans22.size(); i++)
cout << u[ans22[i]] << ' ' << v[ans22[i]] << '\n';*/
int sz11=ans11.size(), sz12=ans12.size(), sz21=ans21.size(), sz22=ans22.size();
int ind=0;
while (ind<min(sz11, sz21) && ans11[ind]==ans21[ind])
ind++;
for (int i=0; i<sz11; i++)
ans.push_back(ans11[i]);
for (int i=0; i<sz12; i++)
ans.push_back(ans12[i]);
for (int i=sz11-1; i>=ind; i--)
ans.push_back(ans11[i]);
for (int i=ind; i<sz21; i++)
ans.push_back(ans21[i]);
for (int i=0; i<sz22; i++)
ans.push_back(ans22[i]);
for (int i=sz21-1; i>=ind; i--)
ans.push_back(ans21[i]);
reverse(ans12.begin(), ans12.end());
reverse(ans22.begin(), ans22.end());
for (int i=ind; i<sz11; i++)
ans.push_back(ans11[i]);
for (int i=0; i<sz12; i++)
ans.push_back(ans12[i]);
for (int i=sz11-1; i>=ind; i--)
ans.push_back(ans11[i]);
for (int i=ind; i<sz21; i++)
ans.push_back(ans21[i]);
for (int i=0; i<sz22; i++)
ans.push_back(ans22[i]);
for (int i=sz21-1; i>=0; i--)
ans.push_back(ans21[i]);
return ans;
}