Submission #825419

#	Time	Username	Problem	Language	Result	Execution time	Memory
825419		tolbi	Split the Attractions (IOI19_split)	C++17	40 / 100	87 ms	17864 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> par(n);
	iota(par.begin(), par.end(), 0);
	vector<int> sz(n,1);
	function<int(int)> find;
	find = [&](int node){
		if (par[node]==node) return node;
		return par[node]=find(par[node]);
	};
	vector<int> ansarr(n,0);
	vector<int> subsz(n);
	vector<vector<int>> arr(n);
	function<int(int,int)> find_centroid;
	find_centroid = [&](int node, int lnode)->int{
		subsz[node]=1;
		int hueh = node;
		for (int i = 0; i < arr[node].size(); i++){
			if (arr[node][i]==lnode) continue;
			int cent = find_centroid(arr[node][i],node);
			if (subsz[arr[node][i]]*2>n) hueh=cent;
			subsz[node]+=subsz[arr[node][i]];
		}
		return hueh;
	};
	for (int i = 0; i < p.size(); i++){
		int u = find(p[i]);
		int v = find(q[i]);
		if (u==v) continue;
		par[u]=v;
		arr[p[i]].push_back(q[i]);
		arr[q[i]].push_back(p[i]);
	}
	iota(par.begin(), par.end(), 0);
	int node = find_centroid(0,-1);
	for (int i = 0; i < n; ++i)
	{
		arr[i].clear();
	}
	for (int i = 0; i < p.size(); i++){
		arr[p[i]].push_back(q[i]);
		arr[q[i]].push_back(p[i]);
	}
	for (int i = 0; i < p.size(); i++){
		if (p[i]==node || q[i]==node) continue;
		int u = find(p[i]);
		int v = find(q[i]);
		if (u==v) continue;
		if (ayahya()%2) swap(u,v);
		par[u]=v;
		sz[v]+=sz[u];
		sz[u]=0;
	}
	array<array<int,2>,3> karr;
	karr[0]={a,1};
	karr[1]={b,2};
	karr[2]={c,3};
	sortarr(karr);
	int node2 = -1;
	for (int i = 0; i < n; i++){
		if (i==node) continue;
		if (sz[i]>=karr[0][0]){
			node2=i;
			if (sz[i]>=karr[1][0]) swap(karr[0],karr[1]);
			break;
		}
	}
	int kalan, filv;
	if (node2==-1){
		return ansarr;
	}
	auto dfs = [&](int crr, int yasak, auto dfs)->void{
		if (!kalan) return;
		if (ansarr[crr]!=karr[2][1]) return;
		if (crr==yasak) return;
		kalan--;
		ansarr[crr]=filv;
		for (int i = 0; i < arr[crr].size(); i++){
			dfs(arr[crr][i],yasak,dfs);
		}
	};
	fill(ansarr.begin(), ansarr.end(), karr[2][1]);
	filv=karr[0][1];
	kalan=karr[0][0];
	dfs(node2,node,dfs);
	assert(kalan==0);
	filv=karr[1][1];
	kalan=karr[1][0];
	dfs(node,-1,dfs);
	assert(kalan==0);
	return ansarr;
}

Compilation message (stderr)

split.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
split.cpp: In lambda function:
split.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   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:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < p.size(); i++){
      |                  ~~^~~~~~~~~~
split.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < p.size(); i++){
      |                  ~~^~~~~~~~~~
split.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 0; i < p.size(); i++){
      |                  ~~^~~~~~~~~~
split.cpp: In instantiation of 'find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, auto:23)> [with auto:23 = find_split(int, int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int, auto:23)>]':
split.cpp:116:20:   required from here
split.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int i = 0; i < arr[crr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~

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