Submission #761849

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
761849	2023-06-20T10:26:15 Z	Red_Inside	Towns (IOI15_towns)	C++17	26 / 100	35 ms	24588 KB

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 mn = inf;
	for(auto v : ver)
	{
		for(auto u : ver)
		{
			if(v.s + u.s - getdist(v.f, u.f) < mn)
			{
				mn = v.s + u.s - getdist(v.f, u.f);
			}
		}
	}
	mn /= 2;
	edges.pb({{V, pred}, mn});
	vector <vector <pii> > seg;
	while(ver.size())
	{
		int v = ver.back().f;
		int d1 = ver.back().s;
		ver.pop_back();
		vector <pii> nw, seg;
		seg.pb({v,d1});
		for(auto i : ver)
		{
			if((i.s+d1-getdist(i.f, v))/2 == mn) nw.pb(i);
			else
				seg.pb(i);
		}
//		cout << "NEW SEG for " << V << endl;
//		for(auto i : seg) cout << i.f << " ";
//		cout << endl;
		ver = nw;
		FOR(0, i, seg.size()) seg[i].s -= mn;
		if(seg.size() == 1)
			edges.pb({{V, seg[0].f}, seg[0].s});
		else
			solve(V, ++cnt, seg);
	}
}

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

void dfs(int v, int pred)
{
	if(edge[v].size() == 1)
		sz[v] = 1;
	else
		sz[v] = 0;
	mxdist[v] = 0;
	dpup[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];
	}
}


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});
//		cout << i.f.f << " " << i.f.s << " " << i.s << endl;
	}
	deep[0] = 0;
	dfs(0, -1);
	dfs2(0);
	ll res = 1e18;
	forn(n, i, cnt)
	{
//		cout << dpup[i] << "  " << mxdist[i] << endl;
		if(max(dpup[i], mxdist[i]) < res) res = max(dpup[i], mxdist[i]);
	}
	forn(n, i, cnt)
	{
		if(res == max(dpup[i], mxdist[i]))
		{
			int ok = 1;
			for(auto to : edge[i])
			{
				if(sz[to.f] > sz[i])
				{
					if(n - sz[i] > n / 2) ok = 0;
				}
				else
				{
					if(sz[to.f] > n / 2) ok = 0;
				}
			}
			if(ok) 
			{
				have = 1;
			}
		}
	}
	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

towns.cpp: In function 'void solve(int, int, std::vector<std::pair<int, int> >)':
towns.cpp:80:20: warning: declaration of 'seg' shadows a previous local [-Wshadow]
   80 |   vector <pii> nw, seg;
      |                    ^~~
towns.cpp:74:25: note: shadowed declaration is here
   74 |  vector <vector <pii> > seg;
      |                         ^~~
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)
......
   92 |   FOR(0, i, seg.size()) seg[i].s -= mn;
      |          ~~~~~~~~~~~~~                 
towns.cpp:92:3: note: in expansion of macro 'FOR'
   92 |   FOR(0, i, seg.size()) seg[i].s -= mn;
      |   ^~~
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)
......
  127 |  FOR(1, i, edge[v].size())
      |         ~~~~~~~~~~~~~~~~~              
towns.cpp:127:2: note: in expansion of macro 'FOR'
  127 |  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)
......
  140 |  FOR(0, i, edge[v].size())
      |         ~~~~~~~~~~~~~~~~~              
towns.cpp:140:2: note: in expansion of macro 'FOR'
  140 |  FOR(0, i, edge[v].size())
      |  ^~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:150:21: warning: declaration of 'n' shadows a global declaration [-Wshadow]
  150 | 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:206:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  206 |  return res * (have ? 1 : -1);
      |         ~~~~^~~~~~~~~~~~~~~~~
towns.cpp:150:28: warning: unused parameter 'sub' [-Wunused-parameter]
  150 | int hubDistance(int n, int sub)
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24416 KB	Output is correct
2	Correct	24 ms	24576 KB	Output is correct
3	Correct	13 ms	23764 KB	Output is correct
4	Correct	26 ms	24588 KB	Output is correct
5	Correct	35 ms	24532 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	23764 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	22 ms	24264 KB	Output is correct
2	Correct	26 ms	24508 KB	Output is correct
3	Correct	11 ms	23764 KB	Output is correct
4	Correct	25 ms	24576 KB	Output is correct