#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const ll M=250000;
vii adj[M];
bool vis[M];
vector<int>ans;
ll n,cntt,root;
ll label[500][500],deg[M];
bool viss[M];
bool visss[M];
void dfs(ll x) {
vis[x]=1;
vii vv;
vector<int>v;
for(int i=0;i<n;i++) {
if(vis[i])
continue;
vv.pb(i);
}
while(vv.size()) {
ll l=0,r=vv.size()-1,mid,res=-1;
res=-1;
while(l<=r) {
for(int i=0;i<n;i++)
viss[i]=0;
v=ans;
mid=((l+r)>>1);
for(int i=r;i>=mid;i--) {
v.pb(label[vv[i]][x]);
viss[vv[i]]=1;
}
for(int i=0;i<n;i++) {
if(!(vis[i]||viss[i]||visss[i])) {
v.pb(label[root][i]);
}
}
ll x=count_common_roads(v);
if(x==cntt) {
r=mid-1;
}
else
l=mid+1,res=mid;
}
if(res==-1)
break;
adj[x].pb(vv[res]);
vis[x]=1;
visss[vv[res]]=1;
ans.pb(label[x][vv[res]]);
cntt++;
while(vv.size()>=res+1)
vv.pop_back();
}
for(auto it:adj[x])
dfs(it);
}
set<ll>s;
ll cnt[M];
vector<int> find_roads(int N, std::vector<int> u, std::vector<int> vv) {
n=N;
if(n==2)
return {0};
for(int i=0;i<u.size();i++)
label[u[i]][vv[i]]=label[vv[i]][u[i]]=i;
for(int i=0;i<n;i++) {
vector<int>v;
for(int j=0;j<n;j++) {
if(j==i)
continue;
v.pb(label[i][j]);
}
deg[i]=count_common_roads(v);
}
for(int i=0;i<n;i++) {
if(deg[i]==1) {
root=i;
}
}
vector<int>v;
for(int i=0;i<n;i++) {
if(i!=root) {
for(int j=0;j<n;j++) {
if(j!=root&&j!=i)
v.pb(label[i][j]);
}
break;
}
}
for(int i=0;i<n;i++) {
if(i==root)
continue;
v.pb(label[i][root]);
ll x=count_common_roads(v);
cnt[label[i][root]]=x;
s.insert(x);
v.pop_back();
}
for(int i=0;i<n;i++) {
if(i==root)
continue;
if(cnt[label[i][root]]==*s.rbegin()) {
adj[root].pb(i);
break;
}
}
memset(vis,0,sizeof vis);
ans.pb(label[adj[root][0]][root]);
vis[root]=1;
cntt=1;
dfs(adj[root][0]);
return ans;
}
/*
5 10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
3 6 8 9
*/
Compilation message
simurgh.cpp: In function 'void dfs(ll)':
simurgh.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
59 | while(vv.size()>=res+1)
| ~~~~~~~~~^~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0;i<u.size();i++)
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
12636 KB |
WA in grader: NO |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
12636 KB |
WA in grader: NO |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
12636 KB |
WA in grader: NO |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8540 KB |
correct |
2 |
Incorrect |
3 ms |
12636 KB |
WA in grader: NO |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
12636 KB |
WA in grader: NO |
2 |
Halted |
0 ms |
0 KB |
- |