Submission #761814

#	Time	Username	Problem	Language	Result	Execution time	Memory
761814		Red_Inside	Towns (IOI15_towns)	C++17	0 / 100	21 ms	24660 KiB

towns

#include "towns.h"
#include <stdio.h>
#include <stdlib.h>

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

#include <bits/stdc++.h>
#include <time.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=1e6+10,LOG=17,mod=1e9+7;
int block = 340, timer = 0;
const double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9+10;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int n, have, dist[500][500], cnt;
vector <pair <pii, int> > edges;
vector <pii> edge[maxn];

int getdist(int v, int u)
{
	if(v == u) return 0;
	if(dist[v][u] != -1) return dist[v][u];
	dist[v][u] = getDistance(v, u);
	dist[u][v] = dist[v][u];
	return dist[v][u];
}

void solve(int pred, int V, vector <pii> ver)
{
//	cout << "SOLVE " << pred << " " << V << endl;
//	for(auto i : ver) cout << i.f << " ";
//	cout << endl;
	int fi = ver.back().f;
	int d1 = ver.back().s;
	ver.pop_back();
	vector <pii> first, second;
	first.pb({fi, d1});
	int mn = inf;
	while(ver.size())
	{
		int v = ver.back().f;
		int d2 = ver.back().s;
		ver.pop_back();
		if((d1+d2-getdist(fi, v)) / 2 < mn)
		{
//			cout << "   " << v << " " << d2 << " " << (d1+d2-getdist(fi, v))/2 << endl;
			mn = (d1+d2-getdist(fi, v)) / 2;
			while(second.size())
			{
				first.pb(second.back());
				second.pop_back();
			}
			second.pb({v, d2});
		}
		else
		if((d1+d2-getdist(fi, v)) / 2 == mn)
		{
			second.pb({v, d2});
		}
		else
		{
			first.pb({v, d2});
		}
	}
	FOR(0, i, first.size())
	{
		first[i].s -= mn;
	}
	FOR(0, i, second.size())
	{
		second[i].s -= mn;
	}
	edges.pb({{pred, V}, mn});
	if(first.size() == 1)
		edges.pb({{first[0].f, V}, first[0].s});
	else
		solve(V, ++cnt, first);
	if(second.size() == 1)
		edges.pb({{second[0].f, V}, second[0].s});
	else
		solve(V, ++cnt, second);
}

int sz[maxn], deep[maxn];
ll mxdist[maxn];

void dfs(int v, int pred)
{
	if(edge[v].size() == 1)
		sz[v] = 1;
	mxdist[v] = 0;
	for(auto to : edge[v])
	{
		if(to.f == pred) continue;
		deep[to.f] = deep[v] + to.s;
		dfs(to.f, v);
		mxdist[v] = max(mxdist[v], mxdist[to.f] + to.s);
		sz[v] += sz[to.f];
	}
	int ok = 1;
	for(auto to : edge[v])
	{
		if(to.f == pred)
		{
			if(n - sz[v] > n / 2) ok = 0;
		}
		else
		{
			if(sz[to.f] > n / 2) ok = 0;
		}
	}
	if(ok) have = 1;
}

ll dpup[maxn];

void dfs2(int v, int pred = -1)
{
	vector <ll> pref(edge[v].size()), suff(edge[v].size());
	pref[0] = (edge[v][0].f == pred ? 0 : mxdist[edge[v][0].f] + edge[v][0].s);
	FOR(1, i, edge[v].size())
	{
		pref[i] = pref[i - 1];
		if(edge[v][i].f == pred) continue;
		pref[i] = max(pref[i], mxdist[edge[v][i].f] + edge[v][i].s);
	}
	suff[(int)edge[v].size() - 1] = (edge[v].back().f == pred ? 0 : mxdist[edge[v].back().f] + edge[v].back().s);
	for(int i = (int)edge[v].size() - 2; i >= 0; --i)
	{
		suff[i] = suff[i + 1];
		if(edge[v][i].f == pred) continue;
		suff[i] = max(suff[i], mxdist[edge[v][i].f] + edge[v][i].s);
	}
	FOR(0, i, edge[v].size())
	{
		pii to = edge[v][i];
		if(to.f == pred) continue;
		
		dpup[to.f] = to.s+max({dpup[v], (i>0?pref[i-1]:0), (i+1<(int)edge[v].size()?suff[i+1]:0)});
		dfs2(to.f, v);
	}
}

int hubDistance(int n, int sub)
{
	have = 0;
	forn(0, i, n-1)
	{
		forn(0, j, n-1)
		{
			dist[i][j] = -1;
		}
	}
	edges.clear();
	cnt = n-1;
	vector <pii> vec;
	forn(1, i, n-1)
	{
		vec.pb({i, getdist(0, i)});
	}
	solve(0, ++cnt, vec);
	forn(0, i, cnt) edge[i].clear();
	for(auto i : edges)
	{
		edge[i.f.f].pb({i.f.s, i.s});
		edge[i.f.s].pb({i.f.f, i.s});
	}
	deep[0] = 0;
	dfs(0, -1);
	dfs2(0);
	int res = 0;
	forn(n, i, cnt)
	{
		if(max(dpup[i], mxdist[i]) > res) res = max(dpup[i], mxdist[i]);
	}
	return res * (have ? 1 : -1);
}

/*
1 1
4
0 35 44 31
35 0 29 16
44 29 0 21
31 16 21 0
*/

Compilation message (stderr)

towns.cpp: In function 'void solve(int, int, std::vector<std::pair<int, int> >)':
towns.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   93 |  FOR(0, i, first.size())
      |         ~~~~~~~~~~~~~~~                
towns.cpp:93:2: note: in expansion of macro 'FOR'
   93 |  FOR(0, i, first.size())
      |  ^~~
towns.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   97 |  FOR(0, i, second.size())
      |         ~~~~~~~~~~~~~~~~               
towns.cpp:97:2: note: in expansion of macro 'FOR'
   97 |  FOR(0, i, second.size())
      |  ^~~
towns.cpp: In function 'void dfs2(int, int)':
towns.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  149 |  FOR(1, i, edge[v].size())
      |         ~~~~~~~~~~~~~~~~~              
towns.cpp:149:2: note: in expansion of macro 'FOR'
  149 |  FOR(1, i, edge[v].size())
      |  ^~~
towns.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  162 |  FOR(0, i, edge[v].size())
      |         ~~~~~~~~~~~~~~~~~              
towns.cpp:162:2: note: in expansion of macro 'FOR'
  162 |  FOR(0, i, edge[v].size())
      |  ^~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:172:21: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  172 | int hubDistance(int n, int sub)
      |                 ~~~~^
towns.cpp:43:5: note: shadowed declaration is here
   43 | int n, have, dist[500][500], cnt;
      |     ^
towns.cpp:202:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  202 |   if(max(dpup[i], mxdist[i]) > res) res = max(dpup[i], mxdist[i]);
      |                                           ~~~^~~~~~~~~~~~~~~~~~~~
towns.cpp:172:28: warning: unused parameter 'sub' [-Wunused-parameter]
  172 | int hubDistance(int n, int sub)
      |                        ~~~~^~~

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