oj.uz

답안 #476310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476310 2021-09-26T02:17:42 Z MonkeyKing Papričice (COCI20_papricice) C++14
50 / 110
 217 ms 15844 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])
//	{
//		chmin(res,calc(m,sz[x],m-sz[x]));
//	}
//	// for(int i=0;i<vv.size();i++) for(int j=i+1;j<vv.size();j++) chmin(res,calc(vv[i],vv[j]));
//	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])
	{
		chmin(res,calc(m,sz[x],m-sz[x]));
	}
	// for(int i=0;i<vv.size();i++) for(int j=i+1;j<vv.size();j++) chmin(res,calc(vv[i],vv[j]));
	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

# 결과 실행 시간 메모리 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 4 ms 4940 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 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 4 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 5060 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 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 4 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 5060 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 212 ms 15600 KB Output is correct
12 Correct 217 ms 15596 KB Output is correct
13 Incorrect 145 ms 15844 KB Output isn't correct
14 Halted 0 ms 0 KB -