# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1100246 | MMihalev | Simurgh (IOI17_simurgh) | C++14 | 3088 ms | 3608 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<iostream>
#include<algorithm>
#include<set>
#include<queue>
#include "simurgh.h"
using namespace std;
const int MAX_N=5e2+3;
const int MAX_M=125000;
int n,m;
int q;
vector<int>edges;
vector<pair<int,int>>g[MAX_N];
bool used[MAX_N];
vector<int>comp;
vector<vector<int>>comps;
int adj[MAX_N];
bool stat[MAX_M];
bool checked[MAX_N];
int forsure;
void reset()
{
comps.clear();
edges.clear();
for(int i=0;i<n;i++)
{
adj[i]=-1;
used[i]=0;
}
}
void dfs(int u)
{
if(adj[u]!=-1)
{
if(!checked[adj[u]])
{
if(stat[adj[u]])while(1);
comp.push_back(adj[u]);
}
if(stat[adj[u]])forsure=adj[u];
}
used[u]=1;
for(auto [v,edge]:g[u])
{
if(used[v])continue;
edges.push_back(edge);
dfs(v);
}
}
void rep(int prev,int edge)
{
for(int i=0;i<edges.size();i++)
{
if(edges[i]==prev){edges[i]=edge;return;}
}
while(1);
}
vector<int> find_roads(int N, vector<int> u, vector<int> v)
{
n=N;
m=u.size();
vector<int>ans;
for(int i=0;i<m;i++)
{
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
for(int u=0;u<n;u++)
{
reset();
used[u]=1;
for(auto [v,edge]:g[u])
{
adj[v]=edge;
}
for(auto [v,edge]:g[u])
{
if(!used[v])
{
forsure=-1;
comp.clear();
dfs(v);
if(forsure!=-1)
{
comp.push_back(forsure);
}
comps.push_back(comp);
}
}
for(auto c:comps)
{
edges.push_back(c[0]);
}
for(auto c:comps)
{
if(q==30000)while(1);
if(edges.size()!=n-1)while(1);
int ma=count_common_roads(edges);q++;
vector<int>marked;
marked.push_back(c[0]);
int prev=c[0];
for(int edge:c)
{
if(edge==c[0])continue;
rep(prev,edge);
if(edges.size()!=n-1)while(1);
if(q==30000)while(1);
int cur=count_common_roads(edges);q++;
if(cur>ma)
{
marked.clear();
ma=cur;
marked.push_back(edge);
}
else if(cur==ma)
{
marked.push_back(edge);
}
prev=edge;
}
for(int edge:marked)stat[edge]=1;
}
for(auto [v,edge]:g[u])checked[edge]=1;
}
for(int i=0;i<m;i++)
{
if(stat[i])ans.push_back(i);
}
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... |