Submission #824565

#	Time	Username	Problem	Language	Result	Execution time	Memory
824565		tolbi	Split the Attractions (IOI19_split)	C++17	11 / 100	56 ms	12952 KiB

split

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
template<typename T> istream& operator>>(istream& is, vector<T> &arr){for (auto &it : arr) is>>it; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> arr){for (auto &it : arr) os<<it<<" "; return os;}
template<typename T,size_t Y> istream& operator>>(istream& is, array<T,Y> &arr){for (auto &it : arr) is>>it; return is;}
template<typename T,size_t Y> ostream& operator<<(ostream& os, array<T,Y> arr){for (auto &it : arr) os<<it<<" "; return os;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it :x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "split.h"

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> rval(n,0);
	int m = p.size();
	vector<vector<int>> arr(n);
	for (int i = 0; i < m; i++){
		arr[p[i]].push_back(q[i]);
		arr[q[i]].push_back(p[i]);
	}
	if (a==1){
		function<void(int)> f;
		vector<bool> vis(n,false);
		int kk = 0;
		f = [&](int node)->void{
			if (kk==b) return;
			vis[node]=true;
			rval[node]=2;
			kk++;
			for (int i = 0; i < arr[node].size(); i++){
				if (vis[arr[node][i]]) continue;
				f(arr[node][i]);
			}
		};
		f(0);
		bool bb = false;
		for (int i = 0; i < n; i++){
			if (rval[i]) continue;
			if (bb) rval[i]=3;
			else rval[i]=1,bb=true;
		}
		return rval;
	}
	if (m!=n-1) return rval;
	fill(rval.begin(), rval.end(), 0);
	array<array<int,2>,3> karr;
	karr[0]={a,1};
	karr[1]={b,2};
	karr[2]={c,3};
	sortarr(karr);
	a=karr[0][0];
	b=karr[1][0];
	vector<int> subsz(n);
	vector<int> boo(n,-1);
	function<void(int,int)> f;
	f = [&](int node, int lnode)->void{
		subsz[node]=1;
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i]==lnode) continue;
			f(arr[node][i],node);
			subsz[node]+=subsz[arr[node][i]];
			if (boo[arr[node][i]]!=-1){
				if (boo[node]==-1) boo[node]=boo[arr[node][i]];
				if (subsz[boo[node]]>subsz[boo[arr[node][i]]]){
					boo[node]=boo[arr[node][i]];
				}
			}
		}
		if (boo[node]==-1 && subsz[node]>=a) boo[node]=node;
	};
	int root = 0;
	for (int i = 0; i < n; i++){
		if (arr[i].size()==1){
			root=i;
			break;
		}
	}
	f(root,-1);
	int k, fil;
	function<void(int)> dfs;
	bool boolean=false;
	dfs = [&](int node)->void{
		if (k==0) return;
		if (rval[node]!=karr[2][1]) return;
		rval[node]=fil;
		k--;
		for (int i = 0; i < arr[node].size(); i++){
			if (subsz[arr[node][i]]>subsz[node] && boolean) continue;
			dfs(arr[node][i]);
		}
	};
	int as = boo[root];
	if (n-subsz[as]>=b){
		fill(rval.begin(), rval.end(), karr[2][1]);
		fil = karr[0][1];
		k=karr[0][0];
		boolean=true;
		dfs(as);
		boolean=false;
		fil = karr[1][1];
		k=karr[1][0];
		dfs(root);
		return rval;
	}
	return rval;
}

Compilation message (stderr)

split.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
split.cpp: In lambda function:
split.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
split.cpp: In lambda function:
split.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
split.cpp: In lambda function:
split.cpp:107:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36