# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
73391 | mr_banana | Simurgh (IOI17_simurgh) | C++17 | 349 ms | 6152 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 <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int MN=1e5+100;
vector<int> adj[MN];
int from[MN],to[MN];
int par[MN],h[MN];
bool mark[MN];
set<int> e;
int n,m;
int vaz[MN];
void dfs(int v){
mark[v]=1;
for(int e1:adj[v]){
int u=from[e1]^to[e1]^v;
if(!mark[u]){
par[u]=e1;
e.insert(e1);
h[u]=h[v]+1;
dfs(u);
}
}
}
int get(){
vector<int> ask;
for(int i:e){
ask.push_back(i);
}
return count_common_roads(ask);
}
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
n=N,m=u.size();
for(int i=0;i<m;i++){
from[i]=u[i];
to[i]=v[i];
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
dfs(0);
memset(vaz,-1,sizeof vaz);
int base=get();
for(int i=0;i<m;i++){
if(e.count(i)==0){
vector<int> path;
vector<int> pans;
int u1=from[i],v1=to[i];
if(h[u1]<h[v1]){
swap(u1,v1);
}
for(int i=h[u1]-h[v1];i>0;i--){
path.push_back(par[u1]);
u1=from[par[u1]]^to[par[u1]]^u1;
}
while(u1!=v1){
path.push_back(par[u1]);
u1=from[par[u1]]^to[par[u1]]^u1;
path.push_back(par[v1]);
v1=from[par[v1]]^to[par[v1]]^v1;
}
for(int j=0;j<path.size();j++){
if((vaz[path[j]]!=-1 && vaz[i]==-1)){
e.erase(path[j]);
e.insert(i);
int x=get();
e.insert(path[j]);
e.erase(i);
if(x<base){
vaz[i]=0;
}
else if(x>base){
vaz[i]=1;
}
else{
vaz[i]=vaz[path[j]];
}
pans.push_back(0);
}
else if(vaz[path[j]]==-1){
e.erase(path[j]);
e.insert(i);
int x=get();
e.insert(path[j]);
e.erase(i);
if(x<base){
vaz[i]=0;
vaz[path[j]]=1;
pans.push_back(0);
}
else if(x>base){
vaz[i]=1;
vaz[path[j]]=0;
pans.push_back(0);
}
else{
pans.push_back(1);
}
}
else{
pans.push_back(0);
}
}
if(vaz[i]==-1){
vaz[i]=0;
}
for(int j=0;j<path.size();j++){
if(pans[j]==1){
vaz[path[j]]=vaz[i];
}
}
}
}
vector<int> ans;
for(int i=0;i<m;i++){
if(vaz[i]!=0){
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... |