oj.uz

Submission #1029000

# Submission time Handle Problem Language Result Execution time Memory
1029000 2024-07-20T11:08:36 Z Dan4Life Towns (IOI15_towns) C++17
26 / 100
 13 ms 1076 KB 
#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;
map<int,set<int>> cnt;
 
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; 

int getD(int i, int pos){
	int i_0 = (dis(0,i)+dis(0,a)-dis(a,i))/2;
	if(i_0<=pos) return dis(a,i)-dis(0,a)+pos;
	return dis(0,i)-pos;
}

bool same(int i, int j, int hubpos){
	int i_u = getD(i,hubpos);
	int u_j = getD(j,hubpos);
	//if(i_u+u_j != dis(i,j)) cout << i << " " << j << "\n";
	return i_u+u_j != dis(i,j);
}

int hubDistance(int N, int sub) {
	n = N; ar2 mx = {0,0}; 
	M.clear(); cnt.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++){
		int i_0 = (dis(0,i)+dis(0,a)-dis(a,i))/2;
		int lpos = dis(0,a) - i_0; 
		int rpos = diameter-lpos;
		M[i_0] = max(lpos, rpos);
		cnt[i_0].insert(i);
	}
	int numHubs = 0;
	for(auto u : M) ans=min(ans, u.second);
	for(auto u : M) if(ans==u.second) numHubs++;
	
	int tot = 0;
	for(auto u : M){
		int pos = u.first, mx_dis = u.second;
		tot+=sz(cnt[pos]);
		if(mx_dis!=ans) continue;
		if(tot-sz(cnt[pos]) > n/2) continue;
		if(n-tot > n/2) continue;
		
		stack<int> S = stack<int>();
		for(int i = 0; i < n; i++) p[i]=i, sz[i]=1;
		/*for(int i = 0; i < n; i++){
			if(sz(S) > n-i) break;
			if(!sz(S)) S.push(i);
			else if(same(S.top(),i,pos)) 
				unionSet(i,S.top()), S.push(i);
			else S.pop();
		}
		if(!sz(S)) continue;
		int i = S.top();*/
		bool ok = 1;
		for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++) 
			if(same(i,j,pos)) unionSet(i,j),ok&=(sz[findSet(i)]<=n/2);
		if(ok) return ans;
		/*
		for(int j = 0; j < n; j++) 
			if(same(i,j,pos)) unionSet(i,j);
		if(sz[findSet(i)]<=n/2) return ans;*/
	}
	return -ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:28: warning: unused parameter 'sub' [-Wunused-parameter]
   44 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 11 ms 348 KB Output is correct
5 Correct 11 ms 348 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Output is correct
2 Correct 13 ms 1040 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 13 ms 1076 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 ms 488 KB Output isn't correct
2 Halted 0 ms 0 KB -