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 "simurgh.h"
#include<iostream>
#include<queue>
using namespace std;
vector<int>r;
vector<int>s;
int c;
int qry(){
for(int i=0; i<r.size() ;i++) r[i]--;
//cout << "QRY: ";
//for(int i=0; i<r.size() ;i++) cout << r[i] << ' ';
//cout << endl;
int ans=count_common_roads(r);
r.clear();r.shrink_to_fit();
//cout << "RES: " << ans << endl;
return ans;
}
int e[501][501];
int g[501][501];
int val[501];
bool sh[501];
int N;
int make(int id){
//cout << "Make " << id << endl;
for(int i=1; i<=id ;i++) sh[i]=false;
for(auto cur:s) sh[cur]=true;
int ext=0;
for(int i=2; i<id ;i++){
if(!sh[i]){
r.push_back(e[1][i]);
ext+=g[1][i];
}
else r.push_back(e[i][id]);
}
if(!sh[1]){
int cur=s[0];
r.push_back(e[1][cur]);
ext+=g[1][cur];
}
else r.push_back(e[1][id]);
for(int i=id+1; i<=N ;i++) r.push_back(e[1][i]);
int res=qry();
s.clear();s.shrink_to_fit();
return res-ext;
}
void tzuyu(int id,int l,int r){
for(int j=l; j<=r ;j++) s.push_back(j);
int cv=make(id)-c;
if(cv==0) return;
if(l==r){
g[l][id]=1;
return;
}
int mid=(l+r)/2;
tzuyu(id,l,mid);
tzuyu(id,mid+1,r);
}
vector<int>find_roads(int n,vector<int> u,vector<int> v){
N=n;
int m=u.size();
if(m!=n*(n-1)/2){
vector<int>rr(n-1);
for(int i=0; i<n-1 ;i++) rr[i]=i;
return rr;
}
if(n==2){r.push_back(0);return r;}
for(int i=0; i<m ;i++) e[u[i]+1][v[i]+1]=e[v[i]+1][u[i]+1]=i+1;
int sum=0;
for(int i=1; i<=n ;i++){
for(int j=1; j<=n ;j++) if(i!=j) r.push_back(e[j][j%n+1]);
val[i]=qry();
sum+=val[i];
}
g[1][2]=sum/(n-1)-val[1];
for(int i=3; i<=n ;i++){
for(int j=1; j<i ;j++) s.push_back(j);
int x=make(i);
for(int j=2; j<i ;j++) s.push_back(j);
int y=make(i);
s.push_back(1);
int z=make(i);
c=y+z-x;
g[1][i]=z-c;
tzuyu(i,2,i-1);
}
for(int i=1; i<=n ;i++)
for(int j=i+1; j<=n ;j++)
if(g[i][j]) r.push_back(e[i][j]-1);
return r;
}
Compilation message (stderr)
simurgh.cpp: In function 'int qry()':
simurgh.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<r.size() ;i++) r[i]--;
~^~~~~~~~~
# | 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... |