Submission #591108

#	Time	Username	Problem	Language	Result	Execution time	Memory
591108		almothana05	Split the Attractions (IOI19_split)	C++14	7 / 100	113 ms	23372 KiB

split

#include "split.h"
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
vector<pair<int , int> >gru;
vector<int> vis;
vector<int>gr[500000];
int re , pl = -1 , maxi = mod , f[500000] ,pl2 , menge;
int unt[300000] , ob[300000];
int dfs(int x){
	int sub = 1;
	vis[x] = 1;
	for(int i = 0 ; i< gr[x].size() ; i ++){
		int kind = gr[x][i];
		if(vis[kind] == 0){
			sub += dfs(kind);
		}
		else{
			f[x] = kind;
		}
	}
	unt[x] = sub;
	ob[x] = menge - unt[x] + 1;
	return sub;
}
void dfs1(int x , int ins){
	if(re <= 0){
		return;
	}
	vis[x] = ins;
	re--;
	for(int i = 0 ; i < gr[x].size() ; i++){
		int kind = gr[x][i];
		if(vis[kind] == 0){
			dfs1(kind , ins);
		}
	}

}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int root;
	menge = n;
	for(int i = 0 ;i < menge ; i++){
		vis.push_back(0);
	}
	gru.push_back({a , 1});
	gru.push_back({b , 2});
	gru.push_back({c , 3});
	sort(gru.begin() , gru.end());
	for(int i = 0 ; i < p.size() ; i++){
		gr[p[i]].push_back(q[i]);
		gr[q[i]].push_back(p[i]);
	}
	for(int i = 0 ; i < menge ; i++){
		if(gr[i].size() > 1){
			root = i;
			break;
		}
	}
	dfs(root);
	for(int x = 0 ; x < menge ; x++){
		vis[x] = 0;
		for(int i = 0 ; i < gr[x].size() ; i++ ){
			int kind = gr[x][i];
			if(kind == f[x]){
				if(unt[x] > gru[0].first && maxi > unt[x]){
					maxi = unt[x];
					pl = x;
					pl2 = kind;
				}
			}
			else{
				if(menge - unt[kind] > gru[0].first && maxi > menge - unt[kind]){
					maxi = menge - unt[kind];
					pl = x;
					pl2 = kind;
				}
			}
		}
	}
	if(maxi == mod){
		return vis;
	}
	vis[pl] = gru[0].second;
	re = gru[1].first;
	dfs1( pl2 , gru[1].second );
	// if(re > 0){
	// 	// assert(gru[2].first >= gru[1].first && gru[1].first > gru[0].first);
	// 	for(int i = 0 ; i < menge ; i++){
	// 		vis[i] =0;
	// 	}
	// 	return vis;
	// }
	re = gru[0].first;
	dfs1(pl , gru[0].second);
	for(int i = 0 ; i < menge ; i ++){
		if(vis[i] == 0){
			vis[i] = gru[2].second;
		}
	}
	return vis;
}

Compilation message (stderr)

split.cpp: In function 'int dfs(int)':
split.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0 ; i< gr[x].size() ; i ++){
      |                  ~^~~~~~~~~~~~~~
split.cpp: In function 'void dfs1(int, int)':
split.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0 ; i < gr[x].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i = 0 ; i < p.size() ; i++){
      |                  ~~^~~~~~~~~~
split.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i = 0 ; i < gr[x].size() ; i++ ){
      |                   ~~^~~~~~~~~~~~~~
split.cpp:61:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |  dfs(root);
      |  ~~~^~~~~~

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