oj.uz

Submission #476312

# Submission time Handle Problem Language Result Execution time Memory
476312 2021-09-26T02:20:50 Z MonkeyKing Papričice (COCI20_papricice) C++14
110 / 110
 244 ms 20264 KB 
//Original Code:
//#include <self/utility>
//#include <self/debug>
//using namespace std;
//int n;
//vector<int> edges[200005];
//int sz[200005];
//int block[200005];
//vector<int> v1,v2;
//
//void calc(int x,int par,vector<int> &v)
//{
//	v.push_back(sz[x]);
//	for(auto u:edges[x])
//	{
//		if(u==par) continue;
//		calc(u,x,v);
//	}
//}
//
//pii go(int x,int par)
//{
//	pii o=mp(n-sz[x],x);
//	pii res=mp(inf,-1);
//	for(auto u:edges[x])
//	{
//		if(u==par) continue;
//		chmax(o.first,sz[u]);
//		chmin(res,go(u,x));
//	}
//	chmin(res,o);
//	return res;
//}
//
//void dfs(int x,int par)
//{
//	sz[x]=1;
//	for(auto u:edges[x])
//	{
//		if(u==par) continue;
//		dfs(u,x);
//		sz[x]+=sz[u];
//	}
//}
//
//int calc(int a,int b,int c)
//{
//	return max({a,b,c})-min({a,b,c});
//}
//
//int calc(const vector<int> &v1,const vector<int> &v2)
//{
//	int res=inf;
//	for(int x:v1)
//	{
//		int m=n-x;
//		int it=lower_bound(all(v2),m/2)-v2.begin();
//		for(int i=max(it-5,0);i<min(it+5,(int)v2.size());i++)
//		{
//			chmin(res,calc(x,v2[i],m-v2[i]));
//		}
//	}
//	return res;
//}
//
//vector<vector<int> > vv;
//int main()
//{
//	freopen("input.txt","r",stdin);
//	cin>>n;
//	for(int i=0;i<n-1;i++)
//	{
//		int x,y;
//		scanf("%d%d",&x,&y);
//		x--;
//		y--;
//		edges[x].emplace_back(y);
//		edges[y].emplace_back(x);
//	}
//	dfs(0,-1);
//	int rt=go(0,-1).second;
//	dfs(rt,-1);
//	sort(all(edges[rt]),[](int x,int y){return sz[x]>sz[y];});
//	for(auto u:edges[rt])
//	{
//		vector<int> t;
//		calc(u,rt,t);
//		sort(all(t));
//		vv.emplace_back(t);
//	}
//	int res=inf;
//	chmin(res,calc(vv[0],vv[1]));
//	int m=n-sz[edges[rt][0]];
//	for(auto x:vv[0])
//	{
//		if(x==sz[edges[rt][0]]) continue;
//		chmin(res,calc(m,x,m-x));
//	}
//	cout<<res<<endl;
//	return 0;
//}

//substituted with C++ Inliner
#ifndef _SELF_UTILITY
#define _SELF_UTILITY 1
#include <numeric>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#include <time.h>
#define Endl endl
#define mp make_pair
#define mt make_tuple
#define ll long long 
#define ull unsigned long long
#define pii pair<int,int>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define quickcin ios_base::sync_with_stdio(false);
#ifdef __TAKE_MOD
int mod;
#else
#ifdef __TAKE_CONST_MOD
const int mod=__TAKE_CONST_MOD;
#else
const int mod=1000000007;
#endif
#endif
const int gmod=3;
const int inf=1039074182;
#ifdef __TAKE_CONST_EPS
const double eps=__TAKE_CONST_EPS;
#else
const double eps=1e-9;
#endif
const double pi=3.141592653589793238462643383279;
const ll llinf=2LL*inf*inf;
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);}
template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;}
template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;}
template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;}
template <typename T> inline T mabs(T x) {return (x<0?-x:x);}
using namespace std;
#endif
#ifndef _SELF_DEBUG
#define _SELF_DEBUG 1
#ifndef _SELF_OPERATOR
#define _SELF_OPERATOR 1
using namespace std;
template <typename T>
ostream & operator<<(ostream &cout, const vector<T> &vec)
{
	cout << "{";
	for (int i = 0; i < (int)vec.size(); i++)
	{
		cout << vec[i];
		if (i != (int)vec.size() - 1)
			cout << ',';
	}
	cout << "}";
	return cout;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &cout, pair<T1, T2> p)
{
	cout << "(" << p.first << ',' << p.second << ")";
	return cout;
}

template <typename T, typename T2>
ostream &operator<<(ostream &cout, set<T, T2> s)
{
	vector<T> t;
	for (auto x : s)
		t.push_back(x);
	cout << t;
	return cout;
}

template <typename T, typename T2>
ostream &operator<<(ostream &cout, multiset<T, T2> s)
{
	vector<T> t;
	for (auto x : s)
		t.push_back(x);
	cout << t;
	return cout;
}

template <typename T>
ostream &operator<<(ostream &cout, queue<T> q)
{
	vector<T> t;
	while (q.size())
	{
		t.push_back(q.front());
		q.pop();
	}
	cout << t;
	return cout;
}

template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &cout, map<T1, T2, T3> m)
{
	for (auto &x : m)
	{
		cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl;
	}
	return cout;
}

template <typename T1, typename T2>
void operator+=(pair<T1, T2> &x,const pair<T1, T2> y)
{
	x.first += y.first;
	x.second += y.second;
}
template <typename T1,typename T2>
pair<T1,T2> operator + (const pair<T1,T2> &x,const pair<T1,T2> &y)
{
	return make_pair(x.first+y.first,x.second+y.second);
}

template <typename T1,typename T2>
pair<T1,T2> operator - (const pair<T1,T2> &x,const pair<T1,T2> &y)
{
	return mp(x.first-y.first,x.second-y.second);
}

template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> x)
{
	return make_pair(-x.first, -x.second);
}

template <typename T>
vector<vector<T>> operator~(vector<vector<T>> vec)
{
	vector<vector<T>> v;
	int n = vec.size(), m = vec[0].size();
	v.resize(m);
	for (int i = 0; i < m; i++)
	{
		v[i].resize(n);
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			v[i][j] = vec[j][i];
		}
	}
	return v;
}
#endif
#include <sstream>
void print0x(int x)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	std::reverse(vec.begin(),vec.end());
	for(int i=0;i<(int)vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}

template <typename T>
void print0x(T x,int len)
{
	std::vector <int> vec;
	while(x)
	{
		std::cout<<(x&1);
		x>>=1;
		len--;
		// vec.push_back(x&1);
		// x>>=1;
	}
	while(len--) cout<<0;
	// reverse(vec.begin(),vec.end());
	// for(int i=(int)vec.size();i<len;i++)
	// {
	// 	putchar('0');
	// }
	// for(size_t i=0;i<vec.size();i++)
	// {
	// 	std::cout<<vec[i];
	// }
	// std::cout<<' ';
}
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#endif
using namespace std;
int n;
vector<int> edges[200005];
int sz[200005];
int block[200005];
vector<int> v1,v2;

void calc(int x,int par,vector<int> &v)
{
	v.push_back(sz[x]);
	for(auto u:edges[x])
	{
		if(u==par) continue;
		calc(u,x,v);
	}
}

pii go(int x,int par)
{
	pii o=mp(n-sz[x],x);
	pii res=mp(inf,-1);
	for(auto u:edges[x])
	{
		if(u==par) continue;
		chmax(o.first,sz[u]);
		chmin(res,go(u,x));
	}
	chmin(res,o);
	return res;
}

void dfs(int x,int par)
{
	sz[x]=1;
	for(auto u:edges[x])
	{
		if(u==par) continue;
		dfs(u,x);
		sz[x]+=sz[u];
	}
}

int calc(int a,int b,int c)
{
	return max({a,b,c})-min({a,b,c});
}

int calc(const vector<int> &v1,const vector<int> &v2)
{
	int res=inf;
	for(int x:v1)
	{
		int m=n-x;
		int it=lower_bound(all(v2),m/2)-v2.begin();
		for(int i=max(it-5,0);i<min(it+5,(int)v2.size());i++)
		{
			chmin(res,calc(x,v2[i],m-v2[i]));
		}
	}
	return res;
}

vector<vector<int> > vv;
int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x--;
		y--;
		edges[x].emplace_back(y);
		edges[y].emplace_back(x);
	}
	dfs(0,-1);
	int rt=go(0,-1).second;
	dfs(rt,-1);
	sort(all(edges[rt]),[](int x,int y){return sz[x]>sz[y];});
	for(auto u:edges[rt])
	{
		vector<int> t;
		calc(u,rt,t);
		sort(all(t));
		vv.emplace_back(t);
	}
	int res=inf;
	chmin(res,calc(vv[0],vv[1]));
	int m=n-sz[edges[rt][0]];
	for(auto x:vv[0])
	{
		if(x==sz[edges[rt][0]]) continue;
		chmin(res,calc(m,x,m-x));
	}
	cout<<res<<endl;
	return 0;
}

Compilation message

papricice.cpp: In function 'int main()':
papricice.cpp:404:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  404 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 203 ms 13184 KB Output is correct
12 Correct 225 ms 13160 KB Output is correct
13 Correct 176 ms 13548 KB Output is correct
14 Correct 180 ms 15624 KB Output is correct
15 Correct 207 ms 15628 KB Output is correct
16 Correct 131 ms 17768 KB Output is correct
17 Correct 199 ms 15784 KB Output is correct
18 Correct 175 ms 20264 KB Output is correct
19 Correct 204 ms 15888 KB Output is correct
20 Correct 244 ms 15812 KB Output is correct