Submission #387441

#	Time	Username	Problem	Language	Result	Execution time	Memory
387441		alishahali1382	Towns (IOI15_towns)	C++14	35 / 100	25 ms	492 KiB

towns

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

typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto abcd_:abcd) cerr<<abcd_<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())

const int inf=1000000010;
const int N=120;

int n, m, k, ans, X, Y;
int D[N][N], pref[N], suff[N];
int par[N];
vector<int> path, vec[N], candid;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int ask(int i, int j){
	if (i==j) return 0;
	if (i>j) swap(i, j);
	if (D[i][j]==-1) D[i][j]=getDistance(i, j);
	return D[i][j];
}
int getpar(int x) { return (par[x]==x?x:par[x]=getpar(par[x]));}
bool check(int u, int v){
	u=getpar(u);
	v=getpar(v);
	if (u==v) return 0;
	if (ask(X, u)+ask(Y, v)-ask(X, Y)-ask(u, v)){
		par[u]=v;
		return 0;
	}
	return 1;
}
int hubDistance(int n, int sub){
	memset(D, -1, sizeof(D));
	memset(pref, 0, sizeof(pref));
	memset(suff, 0, sizeof(suff));
	for (int i=0; i<N; i++) vec[i].clear();
	path.clear();
	candid.clear();

	X=0;
	Y=0;
	for (int i=1; i<n; i++) if (ask(0, i)>ask(0, X)) X=i;
	for (int i=1; i<n; i++) if (ask(X, i)>ask(X, Y)) Y=i;
	ans=inf;
	for (int i=0; i<n; i++){
		int a=(ask(X, i)+ask(X, Y)-ask(Y, i))/2;
		int b=ask(X, Y)-a, c=ask(X, i)-a;
		ans=min(ans, max(a, b));
		path.pb(a);
	}
	if (sub<=2) return ans;
	sort(all(path));
	path.resize(unique(all(path))-path.begin());
	for (int i=0; i<n; i++){
		int a=(ask(X, i)+ask(X, Y)-ask(Y, i))/2;
		int b=ask(X, Y)-a, c=ask(X, i)-a;
		vec[lower_bound(all(path), a)-path.begin()].pb(i);
	}
	// 2n-3 so far
	debugv(path)
	int len=path.size()-1;
	pref[0]=suff[len]=1;
	for (int i=1; i<=len; i++) pref[i]=pref[i-1]+SZ(vec[i]);
	for (int i=len; ~i; i--) suff[i]=suff[i+1]+SZ(vec[i]);
	for (int i=1; i<len; i++) if (max(path[i], ask(X, Y)-path[i])==ans){
		// center at distance vec[i]
		// check for centroid
		if (pref[i-1]>n/2 || suff[i+1]>n/2) continue ;
		if (SZ(vec[i])<=n/2) return ans;
		if (sub==4) continue ;
		// debugv(vec[i])
		/*
		for (int u:vec[i]) for (int v:vec[i])
			cerr<<u<<" "<<v<<"  "<<check(u, v)<<"\n";
		*/
		shuffle(all(vec[i]), rng);
		int v=-1, ted=0;
		for (int u:vec[i]){
			if (v==-1){
				v=u;
				ted=1;
				continue ;
			}
			bool f=check(u, v); // 1 query
			if (!f) ted++;
			else{
				ted--;
				if (!ted) v=-1;
			}
		}
		// debug(v)
		if (v!=-1){
			ted=1;
			for (int u:vec[i]) if (u!=v && !check(u, v)) ted++;
			if (ted>n/2) continue ;
		}
		return ans;
	}
	
	return -ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:41:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   41 | int hubDistance(int n, int sub){
      |                               ^
towns.cpp:18:5: note: shadowed declaration is here
   18 | int n, m, k, ans, X, Y;
      |     ^
towns.cpp:56:22: warning: unused variable 'c' [-Wunused-variable]
   56 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |                      ^
towns.cpp:65:7: warning: unused variable 'b' [-Wunused-variable]
   65 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |       ^
towns.cpp:65:22: warning: unused variable 'c' [-Wunused-variable]
   65 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |                      ^
towns.cpp:70:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   70 |  int len=path.size()-1;
      |          ~~~~~~~~~~~^~

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