oj.uz

Submission #1027956

# Submission time Handle Problem Language Result Execution time Memory
1027956 2024-07-19T11:57:16 Z Dan4Life Towns (IOI15_towns) C++17
35 / 100
 13 ms 540 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
using ar2 = array<int,2>;
const int mxN = 115;
int n, vis[mxN];
int 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 hubDistance(int N, int sub) {
	n = N; ar2 mx = {0,0};
	int a = 0, b = 0; M.clear();
	memset(mem,-1,sizeof(mem));
	for(int i = 0; i < n; i++) 
		mx=max(mx,{dis(a,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]; 
	int diameter = dis(a,b);
	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;
	
	bool ok = 0;
	for(auto u : M){
		int lpos = u.first, mx_dis = u.second;
		int rpos = diameter-lpos;
		if(mx_dis!=ans) continue; ok = 1;
		for(int i = 0; i < n; i++) 
			p[i]=i, sz[i]=1, vis[i]=0;
		for(int i = 0; i < n; i++){
			if(vis[findSet(i)]) continue;
			if(i!=a and i!=b and i!=0) continue;
			int i_u = dis(a,i)-lpos;
			if(dis(a,i)<dis(b,i)) i_u = dis(b,i)-rpos;
			
			for(int j = 0; j < n; j++){
				int u_j = dis(a,j)-lpos;
				if(dis(a,j)<dis(b,j)) u_j = dis(b,j)-rpos;
				if(i_u+u_j != dis(i,j)) unionSet(i,j);
			}
			vis[findSet(i)]=1;
		}
		int x = findSet(a), y = findSet(b), z = findSet(0);
		if(max({sz[x],sz[y],sz[z]})>n/2) return -ans;
		int tot = sz[x]+sz[y]+sz[z]*(z!=x and z!=y);
		int left = n-tot;
		if(left<=n/2) return ans;
		if(sub==4) return -ans;
		
		set<int> comp; comp.clear();
		comp.insert(x), comp.insert(y), comp.insert(z);
		for(int i = 0; i < n; i++){
			int c = findSet(i);
			//if(comp.count(findSet(c))) continue;
			int i_u = dis(a,i)-lpos;
			if(dis(a,i)<dis(b,i)) i_u = dis(b,i)-rpos;
			for(int j = 0; j < n; j++){
				//if(comp.count(findSet(j))) continue;
				int u_j = dis(a,j)-lpos;
				if(dis(a,j)<dis(b,j)) u_j = dis(b,j)-rpos;
				if(i_u+u_j != dis(i,j)) unionSet(i,j);
			}
			comp.insert(findSet(i));
		}
		for(auto i : comp) ok&=(sz[findSet(i)]<=n/2);
		if(ok) return ans;
	}
	return -ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:55:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |   if(mx_dis!=ans) continue; ok = 1;
      |   ^~
towns.cpp:55:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |   if(mx_dis!=ans) continue; ok = 1;
      |                             ^~
towns.cpp:81:8: warning: unused variable 'c' [-Wunused-variable]
   81 |    int c = findSet(i);
      |        ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 344 KB Output is correct
2 Correct 7 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 10 ms 540 KB Output is correct
5 Correct 9 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 7 ms 348 KB Output is correct
3 Correct 9 ms 536 KB Output is correct
4 Correct 10 ms 344 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 528 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -