| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1033769 |
2024-07-25T05:18:50 Z |
vjudge1 |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
604 KB |
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>R;
int N_;
int indexofr[501][501],deg[501];
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){
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()-2*a.size()-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();
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:11:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
11 | assert(R.size()==N_-1);
| ~~~~~~~~^~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0;i<v.size();i+=2){
| ~^~~~~~~~~
simurgh.cpp:55:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=2*a.size();i<v.size();i++)
| ~^~~~~~~~~
simurgh.cpp:62:22: warning: unused variable 'i' [-Wunused-variable]
62 | for(auto i:a)
| ^
simurgh.cpp:67:22: warning: unused variable 'i' [-Wunused-variable]
67 | for(auto i:b)
| ^
simurgh.cpp:69:22: warning: unused variable 'i' [-Wunused-variable]
69 | for(auto i:c)
| ^
simurgh.cpp:71:22: warning: unused variable 'i' [-Wunused-variable]
71 | for(auto i:b)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
