# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1075677 | amin | Simurgh (IOI17_simurgh) | C++17 | 1 ms | 348 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 "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj;
vector<int>q;
int pa[1000000];
int mark[1000000];
int par(int x)
{
if(pa[x]==x)
return x;
pa[x]=par(pa[x]);
return pa[x];
}
void mer(int x,int y)
{
if(x==y)
return ;
pa[y]=x;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
int m=v.size();
vector<int>ans;
while(ans.size()<n-1)
{
// cout<<ans.size()<<endl;
int no=n;
q.clear();
for(int i=0; i<n; i++)
pa[i]=i;
for(int i=0; i<ans.size(); i++)
{
q.push_back(ans[i]);
mer(u[ans[i]],v[ans[i]]);
}
no=n-ans.size();
for(int i=0; i<m; i++)
{
int x=u[i];
int y=v[i];
x=par(x);
y=par(y);
if(x!=y&&no>2)
{
q.push_back(i);
no--;
mer(x,y);
}
}
int co=-1;
stack<int>s;
for(int i=0; i<m; i++)
{
int x=u[i];
int y=v[i];
x=par(x);
y=par(y);
if(mark[i]==0&&x!=y)
{
mark[i]=1;
q.push_back(i);
// s.push(i);
int j=count_common_roads(q);
if(j!=co&&co!=-1)
{
if(j>co)
{
while(!s.empty())
{
s.pop();
}
ans.push_back(i);
}else
{
while(!s.empty())
{
ans.push_back(s.top());
s.pop();
}
}
break;
}
s.push(i);
co=j;
q.pop_back();
}
}
while(!s.empty())
{
ans.push_back(s.top());
s.pop();
}
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |