제출 #824615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
824615		tolbi	Split the Attractions (IOI19_split)	C++17	40 / 100	67 ms	17348 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) {
		fill(rval.begin(), rval.end(), 3);
		int node = 0;
		vector<bool> vis(n,false);
		int kk = 0;
		while (true){
			kk++;
			vis[node]=true;
			if (kk<=a) rval[node]=1;
			else if (kk<=a+b) rval[node]=2;
			else break;
			int nex = -1;
			for (int i = 0; i < arr[node].size(); i++){
				if (vis[arr[node][i]]) continue;
				nex=arr[node][i];
				break;
			}
			if (nex==-1) break;
			node=nex;
		}
		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);
	function<void(int,int)> f;
	vector<int> par(n);
	f = [&](int node, int lnode){
		par[node]=lnode;
		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]];
		}
	};
	function<void(int,int)> dfs;
	int kalan,filv;
	dfs = [&](int node, int lnode){
		if (kalan==0) return;
		rval[node]=filv;
		kalan--;
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i]==lnode) continue;
			dfs(arr[node][i],node);
		}
	};
	f(0,-1);
	bool boolean=false;
	function<void(int,int)> yuppi;
	yuppi = [&](int an, int bn){
		boolean=true;
		fill(rval.begin(), rval.end(), karr[2][1]);
		kalan=karr[0][0];
		filv=karr[0][1];
		dfs(an,bn);
		kalan=karr[1][0];
		filv=karr[1][1];
		dfs(bn,an);
	};
	for (int node = 0; node < n; node++){
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i]==par[node]) continue;
			if (subsz[arr[node][i]]>=a && n-subsz[arr[node][i]]>=b){
				yuppi(arr[node][i],node);
			}
			if (boolean) break;
		}
		if (boolean) break;
		if (node){
			if (subsz[node]>=b && n-subsz[node]>=a){
				yuppi(par[node],node);
			}
		}
		if (boolean) break;
	}
	return rval;
}

컴파일 시 표준 에러 (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 function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for (int i = 0; i < arr[node].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
split.cpp: In lambda function:
split.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
split.cpp: In lambda function:
split.cpp:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:131:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

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