Submission #1068510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068510		noyancanturk	Towns (IOI15_towns)	C++17	100 / 100	89 ms	32636 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];

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 hubDistance(int N, int sub) {
	for(int i=0;i<=1000000;i++)blw[i].clear();
	memset(dist,0,sizeof(dist));
	memset(dp,-1,sizeof(dp));
	memset(legs,-1,sizeof(legs));
	memset(pref,0,sizeof(pref));
	memset(suf,0,sizeof(pref));
	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]=suf[past-i+1]+blw[past-i].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 {
				if(j<i)swap(i,j);
				if(dp[i][j]!=-1)return dp[i][j];
				int k=query(i,j);
				return dp[i][j]=(k!=legs[i]+legs[j]);
			};
			vector<vector<int>>chain1,chain2;
			auto&cmp=blw[cent];
			int m=cmp.size();
			int ind=0;
			while(ind<m){
				if(!chain1.size()||chain1.back().size()==chain2.back().size()){
					if(ind+1==m){
						chain1.pb({cmp[ind]});
						ind++;
					}else{
						bool b=same(cmp[ind],cmp[ind+1]);
						if(b){
							chain1.pb({cmp[ind],cmp[ind+1]});
							chain2.pb({});
						}else{
							chain1.pb({cmp[ind]});
							chain2.pb({cmp[ind+1]});
						}
						ind+=2;
					}
				}else{
					bool b=same(cmp[ind],chain1.back().back());
					if(b){
						chain1.back().pb(cmp[ind]);
					}else{
						chain2.back().pb(cmp[ind]);
					}
					ind++;
				}
			}
			int sz=0;
			for(auto&c:chain1)sz+=c.size();
			if(sz<=maxi)return ans;
			int head=chain1.back().back();
			for(int i=0;i+1<chain1.size();i++){
				if(!same(chain1[i].back(),head)){
					for(int j:chain2[i]){
						sz-=!same(j,head);
					}
				}
				if(sz<=maxi)return ans;
			}
		}
	}
	return -ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:81:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   81 |  pref[0]=blw[0].size();
      |          ~~~~~~~~~~~^~
towns.cpp:82:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   82 |  suf[past]=blw[past].size();
      |            ~~~~~~~~~~~~~~^~
towns.cpp:84:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   84 |   pref[i]=pref[i-1]+blw[i].size();
      |           ~~~~~~~~~^~~~~~~~~~~~~~
towns.cpp:85:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   85 |   suf[past-i]=suf[past-i+1]+blw[past-i].size();
      |               ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
towns.cpp:89:79: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |   if(blw[cent].size()&&pref[cent-1]<=maxi&&suf[cent+1]<=maxi&&blw[cent].size()<=maxi){
      |                                                               ~~~~~~~~~~~~~~~~^~~~~~
towns.cpp: In lambda function:
towns.cpp:100:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  100 |     return dp[i][j]=(k!=legs[i]+legs[j]);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:104:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  104 |    int m=cmp.size();
      |          ~~~~~~~~^~
towns.cpp:133:33: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  133 |    for(auto&c:chain1)sz+=c.size();
      |                                 ^
towns.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |    for(int i=0;i+1<chain1.size();i++){
      |                ~~~^~~~~~~~~~~~~~
towns.cpp:27:28: warning: unused parameter 'sub' [-Wunused-parameter]
   27 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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