| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 73540 |
2018-08-28T11:57:51 Z |
hamzqq9 |
Simurgh (IOI17_simurgh) |
C++14 |
|
30 ms |
5376 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
#define ii pair<int,int>
#define st first
#define nd second
#define pb push_back
#define iii pair<ii,int>
#define all(x) x.begin(),x.end()
#define ppb pop_back
#define ll long long
#define sz(x) ((int)x.size())
using namespace std;
int n,m,inus,ous;
int normal;
vector<int> inmst,path,ans;
int pos[505*505];
int ata[505],ok[505];
vector<iii> rem,e;
vector<ii> v[505];
int flag,reach;
int bul(int x) {
if(ata[x]==x) return x;
return ata[x]=bul(ata[x]);
}
void finish(int w) {
/*for(int i=0;i<sz(path);i++) cerr<<path[i]<<' ';
cerr<<"\n-------------------\n";*/
int bef=0;
vector<int> ress;
for(int i=0;i<sz(path);i++) {
if(bef && ok[path[i]]!=0) {
continue ;
}
bef=max(bef,ok[path[i]]);
swap(inmst[pos[path[i]]],w);
int cur=count_common_roads(inmst);
swap(inmst[pos[path[i]]],w);
/*if(w==2 && path[i]==6) {
//cerr<<"spe "<<normal<<' '<<cur<<'\n'<<pos[6]<<'\n';
/
/(int j=0;j<sz(inmst);j++) cerr<<inmst[j]<<" ";
cerr<<endl;
}*/
ress.pb(cur);
if(cur>normal || (ok[path[i]]==1 && cur==normal)) {
flag=1;
}
if(cur<normal || (ok[path[i]]==2 && cur==normal)) {
flag=-1;
}
}
int pr=0;
if(flag==1) {
for(int i=0;i<sz(path);i++) {
if(ok[path[i]]) continue ;
if(ress[pr]==normal) {
ok[path[i]]=1;
ans.pb(path[i]);
}
else {
ok[path[i]]=2;
}
++pr;
}
}
else if(flag==-1) {
for(int i=0;i<sz(path);i++) {
if(ok[path[i]]) continue ;
if(ress[pr]==normal) {
ok[path[i]]=2;
}
else {
ok[path[i]]=1;
ans.pb(path[i]);
}
++pr;
}
flag=0;
}
else {
for(int i=0;i<sz(path);i++) {
ok[path[i]]=2;
}
}
}
void dfs(int node,int ata,int to,int w) {
if(reach) return ;
if(node==to) {
finish(w);
reach=1;
return ;
}
for(ii i:v[node]) {
if(i.st==ata) continue ;
path.pb(i.nd);
dfs(i.st,node,to,w);
path.ppb();
}
}
void make_mst() {
for(int i=0;i<n;i++) ata[i]=i;
for(auto i:e) {
if(bul(i.st.st)!=bul(i.st.nd)) {
inmst.pb(i.nd);
pos[i.nd]=sz(inmst)-1;
//cerr<<i.nd<<' '<<pos[i.nd]<<endl;
ata[bul(i.st.st)]=bul(i.st.nd);
v[i.st.st].pb({i.st.nd,i.nd});
v[i.st.nd].pb({i.st.st,i.nd});
}
else {
rem.pb(i);
}
}
normal=count_common_roads(inmst);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
m=sz(u);
::n=n;
for(int i=0;i<m;i++) {
e.pb({{u[i],v[i]},i});
}
random_shuffle(all(e));
make_mst();
//cerr<<normal<<endl;
//cerr<<"----------------\n";
//for(int i=0;i<sz(inmst);i++) cerr<<inmst[i]<<endl;
//cerr<<"---------------\n";
for(auto edge:rem) {
flag=0;
reach=0;
//cerr<<edge.nd<<endl;
dfs(edge.st.st,-1,edge.st.nd,edge.nd);
if(flag) {
ans.pb(edge.nd);
}
if(sz(ans)==n-1) break ;
}
//cerr<<"-----------------\n";
for(int i=0;i<sz(inmst);i++) if(sz(ans)!=n-1 && !ok[inmst[i]]) ans.pb(inmst[i]);
//for(int i=0;i<sz(ans);i++) cerr<<ans[i]<<endl;
assert(sz(ans)==n-1);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
456 KB |
correct |
| 3 |
Correct |
3 ms |
524 KB |
correct |
| 4 |
Incorrect |
2 ms |
524 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
456 KB |
correct |
| 3 |
Correct |
3 ms |
524 KB |
correct |
| 4 |
Incorrect |
2 ms |
524 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
456 KB |
correct |
| 3 |
Correct |
3 ms |
524 KB |
correct |
| 4 |
Incorrect |
2 ms |
524 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
524 KB |
correct |
| 2 |
Correct |
2 ms |
524 KB |
correct |
| 3 |
Incorrect |
30 ms |
5376 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Correct |
2 ms |
456 KB |
correct |
| 3 |
Correct |
3 ms |
524 KB |
correct |
| 4 |
Incorrect |
2 ms |
524 KB |
WA in grader: NO |
| 5 |
Halted |
0 ms |
0 KB |
- |
