| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 565214 |
2022-05-20T13:06:01 Z |
jamezzz |
Simurgh (IOI17_simurgh) |
C++17 |
|
291 ms |
5544 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef pair<int,int> ii;
#define maxn 505
struct UFDS{
int par[maxn],rnk[maxn];
void init(int n){
for(int i=0;i<n;++i)par[i]=i,rnk[i]=1;
}
int fp(int i){
return (par[i]==i)?i:par[i]=fp(par[i]);
}
void join(int x,int y){
x=fp(x),y=fp(y);
if(x==y)return;
if(rnk[x]<rnk[y])par[x]=y;
else par[y]=x;
if(rnk[x]==rnk[y])++rnk[x];
}
}ufds;
int n,m,good[maxn*maxn],edge[maxn][maxn];
int par[maxn],depth[maxn],deg[maxn],done[maxn];
vector<int> AL[maxn];
vector<ii> EL,back_edge,tree_edge;
void dfs(int u){
int far=u;
for(int v:AL[u]){
if(depth[v]==0){
par[v]=u;
depth[v]=depth[u]+1;
dfs(v);
tree_edge.pb({u,v});
}
else if(v!=par[u]&&depth[far]>depth[v])far=v;
}
back_edge.pb({u,far});
}
int count(vector<int> e){
int num=0;
ufds.init(n);
vector<int> ask;
for(int i:e){
int u,v;
tie(u,v)=EL[i];
ufds.join(u,v);
ask.pb(edge[u][v]);
}
for(auto[u,v]:tree_edge){
if(ufds.fp(u)!=ufds.fp(v)){
ufds.join(u,v);
ask.pb(edge[u][v]);
num+=good[edge[u][v]];
}
}
return count_common_roads(ask)-num;
}
vector<int> find_roads(int _n,vector<int> u,vector<int> v){
n=_n;m=u.size();
memset(edge,-1,sizeof edge);
memset(good,-1,sizeof good);
for(int i=0;i<m;++i){
AL[u[i]].pb(v[i]);
AL[v[i]].pb(u[i]);
edge[u[i]][v[i]]=edge[v[i]][u[i]]=i;
EL.pb({u[i],v[i]});
}
depth[0]=1;
dfs(0);
for(auto[u,v]:back_edge){
if(u==v)continue;
vector<ii> edges;
edges.pb({u,v});
ufds.init(n);
while(u!=v){
edges.pb({u,par[u]});
ufds.join(u,par[u]);
u=par[u];
}
vector<ii> others;
for(auto[u,v]:EL){
if(ufds.fp(u)!=ufds.fp(v)){
others.pb({u,v});
ufds.join(u,v);
}
}
vector<ii> res;
bool have_ref=false;
for(auto[u,v]:edges){
int id=edge[u][v];
if(good[id]==0)continue;
if(good[id]==1&&have_ref)continue;
if(good[id]==1)have_ref=true;
vector<int> ask;
for(auto[u,v]:others)ask.pb(edge[u][v]);
for(auto[x,y]:edges){
if(x!=u||y!=v)ask.pb(edge[x][y]);
}
res.pb({count_common_roads(ask),id});
}
if(res.size()==0)continue;
sort(res.begin(),res.end());
int small=res[0].fi;
for(auto[x,i]:res){
if(x==small)good[i]=1;
else good[i]=0;
}
}
for(int u=0;u<n;++u){
vector<int> tmp;
for(int v:AL[u])tmp.pb(edge[u][v]);
deg[u]=count(tmp);
}
while(true){
int u=-1;
for(int i=0;i<n;++i){
if(done[i]==0&°[i]==1)u=i;
}
if(u==-1)break;
vector<int> e;
for(int v:AL[u]){
if(!done[v])e.pb(edge[u][v]);
}
int lo=0,hi=e.size()-1,mid,res;
while(lo<=hi){
mid=(lo+hi)>>1;
vector<int> tmp;
for(int i=0;i<=mid;++i)tmp.pb(e[i]);
if(count(tmp)==1)res=mid,hi=mid-1;
else lo=mid+1;
}
good[e[res]]=1;
int v=EL[e[res]].fi;
if(u==v)v=EL[e[res]].se;
--deg[v];
done[u]=1;
}
vector<int> ans;
for(int i=0;i<m;++i){
if(good[i]==1)ans.pb(i);
}
assert(count_common_roads(ans)==n-1);
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:149:13: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
149 | good[e[res]]=1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2260 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2260 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2260 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2260 KB |
correct |
| 2 |
Correct |
2 ms |
2260 KB |
correct |
| 3 |
Incorrect |
291 ms |
5544 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2260 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
