Submission #1028117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028117	2024-07-19T13:57:55 Z	Dan4Life	Towns (IOI15_towns)	C++17	Compilation error	0 ms	0 KB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
using ar2 = array<int,2>;
const int mxN = 115;
int n, mem[mxN][mxN];
map<int,int> M;
 
int dis(int a, int b){
	if(a==b) return 0;
	if(mem[a][b]!=-1) return mem[a][b];
	if(mem[b][a]!=-1) return mem[b][a];
	return mem[a][b]=mem[b][a]=getDistance(a,b);
}
 
int p[mxN], sz[mxN];
int findSet(int i) { return p[i]==i?i:p[i]=findSet(p[i]); }
bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }
 
void unionSet(int i, int j){
	int x = findSet(i), y = findSet(j);
	if(x==y) return;
	if(sz[x]<sz[y]) swap(x,y);
	p[y]=x; sz[x]+=sz[y];
}

int a, b, diameter; 
bool same(int i, int j, int lpos){
	int rpos = diameter-lpos;
	int i_u = dis(a,i)-lpos;
	if(dis(a,i)<dis(b,i)) i_u = dis(b,i)-rpos;
	int u_j = dis(a,j)-lpos;
	if(dis(a,j)<dis(b,j)) u_j = dis(b,j)-rpos;
	return i_u+u_j != dis(i,j);
}

int hubDistance(int N, int sub) {
	n = N; ar2 mx = {0,0};
	a = 0, b = 0; M.clear();
	memset(mem,-1,sizeof(mem));
	for(int i = 0; i < n; i++) 
		mx=max(mx,{dis(0,i),i});
	a = mx[1]; mx = {0,0};
	for(int i = 0; i < n; i++)
		mx=max(mx,{dis(a,i),i});
	b = mx[1]; diameter = mx[0];
	int ans = diameter;
 
	for(int i = 0; i < n; i++){
		if(i==a or i==b) continue;
		int branch = (dis(a,i)+dis(b,i)-diameter)/2;
		int lpos = dis(a,i)-branch;
		int rpos = diameter-lpos;
		M[lpos]=max({M[lpos],branch,lpos,rpos});
	}
	for(auto u : M) ans=min(ans,u.second);
	if(sub<=2) return ans;
	
	for(auto u : M){
		int lpos = u.first, mx_dis = u.second;
		if(mx_dis!=ans) continue;
		
		for(int i = 0; i < n; i++) p[i]=i, sz[i]=1;
		
		if(sub==4){
			for(int i = 0; i < n; i++){
				if(i!=a and i!=b) continue;
				for(int j = 0; j < n; j++)
					if(same(i,j,lpos)) unionSet(i,j);
			}
			if(sz[findSet(a)]>n/2) return -ans;
			if(sz[findSet(b)]>n/2) return -ans;
			int tot = sz[findSet(a)]+sz[findSet(b)];
			int left = n-tot;
			if(left>n/2) return -ans;
			return ans;
		}
		
		stack<int> S = stack<int>();
		for(int i = 0; i < n; i++){
			if(sz(S) > n-i) return ans;
			if(!sz(S) or same(S.top(),i,lpos)) 
				unionSet(i,S.top()), S.push(i);
			else S.pop();
		}
		if(sz(S) and sz[findSet(S.top()]<=n/2) return ans;
	}
	return -ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:87:34: error: expected ')' before ']' token
   87 |   if(sz(S) and sz[findSet(S.top()]<=n/2) return ans;
      |                          ~       ^
      |                                  )
towns.cpp:88:2: error: expected primary-expression before '}' token
   88 |  }
      |  ^
towns.cpp:87:53: error: expected ')' before '}' token
   87 |   if(sz(S) and sz[findSet(S.top()]<=n/2) return ans;
      |     ~                                               ^
      |                                                     )
   88 |  }
      |  ~                                                   
towns.cpp:88:2: error: expected primary-expression before '}' token
   88 |  }
      |  ^