Submission #95917

#	Time	Username	Problem	Language	Result	Execution time	Memory
95917		jangwonyoung	Simurgh (IOI17_simurgh)	C++14	19 / 100	124 ms	5140 KiB

simurgh

#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]--;
               ~^~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30