Submission #909758

#	Time	Username	Problem	Language	Result	Execution time	Memory
909758		Wansur	Towns (IOI15_towns)	C++14	35 / 100	14 ms	1116 KiB

towns

#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

#pragma once
using namespace std;
typedef long long ll;
const int mx=212;

int p[mx];
int sz[mx];
int d[mx][mx];
bool was[mx][mx];
int cnt;

int getDistance(int i, int j);

void upd(int i,int j){
	if(was[i][j])return;
	was[i][j]=was[j][i]=1;
	cnt++;
	d[i][j]=d[j][i]=getDistance(i,j);
}

int get(int x){
	if(p[x]==x)return x;
	return p[x]=get(p[x]);
}

void merge(int a,int b){
	if(get(a)==get(b))return;
	sz[get(b)]+=sz[get(a)];
	p[get(a)]=get(b);
}

int hubDistance(int n, int sub){
	cnt=0;
	for(int i=0;i<n;i++){
		p[i]=i;
		sz[i]=1;
		for(int j=0;j<n;j++){
			was[i][j]=0;
			d[i][j]=-1;
			if(i==j){
				was[i][j]=1;
				d[i][j]=0;
			}
		}
	}
	int v=0,u=0;
	for(int i=1;i<n;i++){
		upd(0,i);
		if(d[0][i]>d[0][v]){
			v=i;
		}
	}
	for(int i=0;i<n;i++){
		upd(v,i);
		if(d[v][i]>d[v][u]){
			u=i;
		}
	}
	for(int i=0;i<n;i++){
		upd(u,i);
	}
	int ans=2e9;
	int mid=0;
	for(int i=0;i<n;i++){
		int t=d[v][i]+d[i][u]-d[v][u];
		ans=min(ans,max(d[v][i],d[i][u])-t/2);
		if(ans==max(d[v][i],d[i][u])-t/2){
			mid=d[v][i]-t/2;
		}
	}
	if(sub==3 || sub==1){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				upd(i,j);
			}
		}
		int c1=0,c2=0,c3=0;
		vector<pair<int,int>> ord;
		for(int i=0;i<n;i++){
			int t=(d[v][i]+d[i][u]-d[v][u]);
			if(d[v][i]-t/2<mid)c1++;
			else if(d[v][i]-t/2==mid){
				ord.push_back({i,t/2});
			}
			else c3++;
		}
		for(auto x:ord){
			for(auto y:ord){
				ll v=x.f,u=y.f,dist=x.s+y.s;
				if(dist!=d[v][u]){
					merge(v,u);
				}
			}
		}
		set<int> s;
		for(auto x:ord){
			s.insert(get(x.f));
		}
		for(auto v:s){
			c2=max(c2,sz[v]);
		}
		if(max({c1,c2,c3})>n/2)ans*=-1;
		assert(cnt<=n*(n-1)/2);
		return ans;
	}
	int c1=0,c2=0,c3=0;
	for(int i=0;i<n;i++){
		int t=(d[v][i]+d[i][u]-d[v][u]);
		if(d[v][i]-t/2<mid)c1++;
		else if(d[v][i]-t/2==mid)c2++;
		else c3++;
	}
	if(max({c1,c2,c3})>n/2)ans*=-1;
	return ans;
}

Compilation message (stderr)

towns.cpp:6:9: warning: #pragma once in main file
    6 | #pragma once
      |         ^~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:94:8: warning: declaration of 'v' shadows a previous local [-Wshadow]
   94 |     ll v=x.f,u=y.f,dist=x.s+y.s;
      |        ^
towns.cpp:51:6: note: shadowed declaration is here
   51 |  int v=0,u=0;
      |      ^
towns.cpp:94:14: warning: declaration of 'u' shadows a previous local [-Wshadow]
   94 |     ll v=x.f,u=y.f,dist=x.s+y.s;
      |              ^
towns.cpp:51:10: note: shadowed declaration is here
   51 |  int v=0,u=0;
      |          ^
towns.cpp:96:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   96 |      merge(v,u);
      |            ^
towns.cpp:96:14: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   96 |      merge(v,u);
      |              ^
towns.cpp:104:12: warning: declaration of 'v' shadows a previous local [-Wshadow]
  104 |   for(auto v:s){
      |            ^
towns.cpp:51:6: note: shadowed declaration is here
   51 |  int v=0,u=0;
      |      ^

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