Submission #1068193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068193		noyancanturk	Towns (IOI15_towns)	C++17	25 / 100	88 ms	24956 KiB

towns

#include "towns.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

int n;

int dist[200][200];

const int lim=1e6+100;

int pref[lim],suf[lim];
vector<int>blw[lim];
vector<int>dudes[200];

int query(int i,int j){
	if(i==j)return 0;
	if(j<i)swap(i,j);
	if(!dist[i][j])dist[i][j]=getDistance(i,j);
	return dist[i][j];
}

int dp[200][200];
int legs[200];

int parent[200];
int find(int i){
	if(i==parent[i])return i;
	return parent[i]=find(parent[i]);
}
void unite(int i,int j){
	i=find(i),j=find(j);
	if(i^j){
		parent[j]=i;
		for(int k:dudes[j])dudes[i].pb(k);
	}
}

int hubDistance(int N, int sub) {
	for(int i=0;i<=1000000;i++)blw[i].clear();
	for(int i=0;i<200;i++){
		dudes[i].clear();
		dudes[i].pb(i);
	}
	memset(dist,0,sizeof(dist));
	memset(dp,-1,sizeof(dp));
	memset(legs,-1,sizeof(legs));
	for(int i=0;i<N;i++)parent[i]=i;
	n=N;
	int past=-1,point1=-1;
	for(int i=1;i<n;i++){
		if(past<query(0,i)){
			point1=i;
			past=query(0,i);
		}
	}
	past=-1;
	int point2=-1;
	for(int i=0;i<n;i++){
		if(i==point1)continue;
		if(past<query(point1,i)){
			point2=i;
			past=query(point1,i);
		}
	}
	int legsize=0;
	int dist0=query(0,point1);
	if(point2){
		int dist1=query(0,point1),dist2=query(0,point2);
		int ss=dist1+dist2;
		legsize=(ss-past)/2;
		legs[0]=legsize;
		dist0-=legsize;
	}
	blw[0].pb(point1);
	blw[past].pb(point2);
	for(int i=0;i<n;i++){
		if(i==point1||i==point2)continue;
		int ds0=query(0,i),ds1=query(point1,i);
		int legi=(ds0+ds1-query(0,point1))/2;
		int pure0=ds0-legi,pure1=ds1-legi;
		if(pure0<legsize){
			legs[i]=ds1-dist0;
			blw[dist0].pb(i);
		}else{
			legs[i]=legi;
			blw[pure1].pb(i);
		}
	}
	int ans=past;
	for(int i=0;i<past;i++){
		if(blw[i].size()&&max(i,past-i)<ans){
			ans=max(i,past-i);
		}
	}
	pref[0]=blw[0].size();
	suf[past]=blw[past].size();
	for(int i=1;i<=past;i++){
		pref[i]=pref[i-1]+blw[i].size();
		suf[past-i-1]=suf[past-i]+blw[past-i-1].size();
	}
	int maxi=n/2;
	for(int cent:{ans,past-ans}){
		if(blw[cent].size()&&pref[cent-1]<=maxi&&suf[cent+1]<=maxi&&blw[cent].size()<=maxi){
			return ans;
		}
	}
	for(int cent:{ans,past-ans}){
		if(blw[cent].size()&&pref[cent-1]<=maxi&&suf[cent+1]<=maxi){
			//cerr<<"building "<<cent<<"\n";
			auto same=[&](int i,int j)->bool {
				i=find(i),j=find(j);
				for(int x:dudes[i]){
					for(int y:dudes[j]){
						if(dp[x][y]!=-1){
							if(dp[x][y])unite(x,y);
							return dp[x][y];
						}
					}
				}
				int k=query(i,j);
				bool val=(k!=legs[i]+legs[j]);
				dp[i][j]=dp[j][i]=val;
				if(val){
					unite(i,j);
				}
				return val;
			};
			vector<int>chain1,chain2;
			auto&cmp=blw[cent];
			int m=cmp.size();
			int ind=0;
			while(ind<m){
				if(chain1.size()==chain2.size()){
					//cerr<<"eq ";
					if(ind+1==m){
						//cerr<<cmp[ind]<<" only\n";
						chain1.pb(cmp[ind]);
						ind++;
					}else{
						bool b=same(cmp[ind],cmp[ind+1]);
						//cerr<<cmp[ind]<<" "<<cmp[ind+1]<<" is "<<b<<"\n";
						if(b){
							chain1.pb(cmp[ind]);
							chain1.pb(cmp[ind+1]);
						}else{
							chain1.pb(cmp[ind]);
							chain2.pb(cmp[ind+1]);
						}
						ind+=2;
					}
				}else{
					//cerr<<"chaining "<<cmp[ind]<<" "<<chain1.back()<<" ";
					bool b=same(cmp[ind],chain1.back());
					//cerr<<b<<"\n";
					if(b){
						chain1.pb(cmp[ind]);
					}else{
						chain2.pb(cmp[ind]);
					}
					ind++;
				}
			}
			if(chain1.size()<=maxi)return ans;
			int sz=chain1.size();
			int head=chain1.back();
			for(int j=sz-2;0<=j;j--){
				if(!same(chain1[j],head)&&!(j<chain2.size()&&same(chain2[j],head))){
					sz--;
				}
			}
			if(sz<=maxi)return ans;
		}
	}
	return -ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:98:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   98 |  pref[0]=blw[0].size();
      |          ~~~~~~~~~~~^~
towns.cpp:99:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   99 |  suf[past]=blw[past].size();
      |            ~~~~~~~~~~~~~~^~
towns.cpp:101:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  101 |   pref[i]=pref[i-1]+blw[i].size();
      |           ~~~~~~~~~^~~~~~~~~~~~~~
towns.cpp:102:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  102 |   suf[past-i-1]=suf[past-i]+blw[past-i-1].size();
      |                 ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
towns.cpp:106:79: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |   if(blw[cent].size()&&pref[cent-1]<=maxi&&suf[cent+1]<=maxi&&blw[cent].size()<=maxi){
      |                                                               ~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:133:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  133 |    int m=cmp.size();
      |          ~~~~~~~~^~
towns.cpp:166:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  166 |    if(chain1.size()<=maxi)return ans;
      |       ~~~~~~~~~~~~~^~~~~~
towns.cpp:167:22: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  167 |    int sz=chain1.size();
      |           ~~~~~~~~~~~^~
towns.cpp:170:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     if(!same(chain1[j],head)&&!(j<chain2.size()&&same(chain2[j],head))){
      |                                 ~^~~~~~~~~~~~~~
towns.cpp:41:28: warning: unused parameter 'sub' [-Wunused-parameter]
   41 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39