#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>R;
int N_;
int indexofr[601][601],deg[601];
void AD(int x,int y){
R.push_back(indexofr[x][y]);
}
int Q(){ assert(R.size()==N_-1);
return count_common_roads(R);
}
void die(vector<int>k,int x){
for(auto i:k)
AD(x,i);
}
vector<int>ans;
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N_=n;
int m=u.size();
for(int i=0;i<m;i++)
indexofr[u[i]][v[i]]=indexofr[v[i]][u[i]]=i;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
if(j-i)AD(i,j);
deg[i]=Q();
R.clear();
}
set<int>st;
for(int i=0;i<n;i++)
st.insert(i);
vector<int>done;
for(int i=1;i<n;i++){
int x=0;
for(int i=0;i<n;i++)
if(deg[i]==1)x=i;
R.clear();
deg[x]=0;
st.erase(x);
die(done,x);
done.push_back(x);
vector<int>v;
for(auto i:st)
v.push_back(i);
while(v.size()>1){
assert(R.size()+v.size()==N_-1);
int origsz=R.size();
vector<int>a,b,c;
for(int i=0;i<v.size();i+=2){
a.push_back(v[i]);
b.push_back(v[i+1]);
AD(v[i],v[i+1]);
if(v.size()-3*a.size()<=1)
break;
}
for(int i=2*a.size();i<v.size();i++)
c.push_back(v[i]);
for(auto i:c)
AD(x,i);
for(auto i:a)
AD(x,i);
int A=Q();
for(auto i:a)
R.pop_back();
for(auto i:b)
AD(x,i);
A-=Q();
for(auto i:b)
R.pop_back();
for(auto i:c)
R.pop_back();
for(auto i:b)
R.pop_back();
int K=R.size();
assert(origsz==K);
if(A<0) die(a,x),
die(c,x),v=b;
else if(A)die(b,x),
die(c,x),v=a;
else die(a,x),die(b,x),v=c;
}
deg[v[0]]--;
ans.push_back(indexofr[x][v[0]]);
}
return ans;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from simurgh.cpp:2:
simurgh.cpp: In function 'int Q()':
simurgh.cpp:10:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
10 | int Q(){ assert(R.size()==N_-1);
| ~~~~~~~~^~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:46:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | assert(R.size()+v.size()==N_-1);
| ~~~~~~~~~~~~~~~~~^~~~~~
simurgh.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i=0;i<v.size();i+=2){
| ~^~~~~~~~~
simurgh.cpp:56:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=2*a.size();i<v.size();i++)
| ~^~~~~~~~~
simurgh.cpp:63:22: warning: unused variable 'i' [-Wunused-variable]
63 | for(auto i:a)
| ^
simurgh.cpp:68:22: warning: unused variable 'i' [-Wunused-variable]
68 | for(auto i:b)
| ^
simurgh.cpp:70:22: warning: unused variable 'i' [-Wunused-variable]
70 | for(auto i:c)
| ^
simurgh.cpp:72:22: warning: unused variable 'i' [-Wunused-variable]
72 | for(auto i:b)
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
