oj.uz

Submission #744991

# Submission time Handle Problem Language Result Execution time Memory
744991 2023-05-19T09:33:48 Z myrcella Towns (IOI15_towns) C++17
100 / 100
 16 ms 896 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}


const int maxn = 111;

#include "towns.h"

int u=0,n;
int dis[maxn][maxn];
vector <pii> nodee;

int getdis(int x,int y) {
	if (x==y) return 0;
	if (dis[x][y]==-1) dis[x][y] = dis[y][x] = getDistance(x,y);
	return dis[x][y];
}

bool samebranch(int x,int y,int R) {
	if (getdis(x,u) + getdis(y,u) - getdis(x,y) > 2*R) return true;
	assert(getdis(x,u) + getdis(y,u) - getdis(x,y) == 2*R); 
	return false;
}

bool check(int R) {
	int cnt = 0;
	vector <pii> node = nodee;
	while (!node.empty() and node.back().fi!=R) cnt++,node.pop_back();
	if (cnt*2>n) return false;
	cnt = 0;
	reverse(ALL(node));
	while (!node.empty() and node.back().fi!=R) cnt++,node.pop_back();
	if (cnt*2>n) return false;
	vector <pii> alive,dead;
	for (auto it:node) alive.pb({it.se,1});
	/*for (auto it:node) {
		int cnt=0;
		for (auto itt:node) if (samebranch(it.se,itt.se,R)) {
			cnt++;
			//cout<<itt.se<<" ";
		}
		if (cnt*2>n) cout<<it.se<<" ";
	}*/
	while (1) {
		if (SZ(alive)<=1) break;
		vector <pii> tmp;
		while (SZ(alive)>1) {
			auto it1 = alive.back();alive.pop_back();
			auto it2 = alive.back();alive.pop_back();
			
			if (samebranch(it1.fi,it2.fi,R)) {
				tmp.pb({it1.fi,it1.se + it2.se});
				if ((it1.se + it2.se)*2>n) return false;
			}
			else {
				if (it1.se>it2.se) swap(it1,it2);
				if (it1.se==it2.se) dead.pb(it1),dead.pb(it2);
				else dead.pb(it1),dead.pb({it2.fi,it1.se}),tmp.pb({it2.fi,it2.se-it1.se});
			}
		}
		while (!tmp.empty()) alive.pb(tmp.back()),tmp.pop_back();
	}
	if (alive.empty()) return true;
	cnt = alive[0].se;
	if (cnt*2>n) return false;
	for (auto it:dead) {
		if (samebranch(it.fi,alive[0].fi,R)) {
			cnt += it.se;
			if (cnt*2>n) return false;
		}
	}
	return true;
}

int hubDistance(int N, int sub) {
	n = N;
	u = 0;
	memset(dis,-1,sizeof(dis));
	rep(i,0,N) if (getdis(0,i) > getdis(0,u)) u = i;
	int diam = 0;
	rep(i,0,N) diam = max(diam,getdis(i,u));
	int ans = mod;
	//find centre
	nodee.clear();
	rep(i,0,N) {
		int disi0 = getdis(i,0), disu0 = getdis(u,0), disui = getdis(u,i);
		int cur = (disu0 + disui - disi0)/2;
		assert((disu0+disui-disi0)%2==0);
		nodee.pb({cur,i});
		ans = min(ans,max(cur,diam-cur));
	}
	sort(ALL(nodee));
	if (check(ans) or check(diam-ans)) return ans;
	else return -ans;
}

Compilation message

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

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 400 KB Output is correct
2 Correct 10 ms 552 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 14 ms 456 KB Output is correct
5 Correct 13 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 13 ms 452 KB Output is correct
3 Correct 16 ms 404 KB Output is correct
4 Correct 15 ms 416 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 15 ms 492 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 896 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 15 ms 464 KB Output is correct
3 Correct 14 ms 836 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 396 KB Output is correct
2 Correct 14 ms 448 KB Output is correct
3 Correct 15 ms 852 KB Output is correct