oj.uz

Submission #591108

# Submission time Handle Problem Language Result Execution time Memory
591108 2022-07-06T21:32:26 Z almothana05 Split the Attractions (IOI19_split) C++14
7 / 100
 113 ms 23372 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 6 ms 11988 KB ok, correct split
3 Correct 6 ms 12016 KB ok, correct split
4 Correct 6 ms 11988 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 6 ms 11988 KB ok, correct split
7 Correct 74 ms 23108 KB ok, correct split
8 Correct 65 ms 21744 KB ok, correct split
9 Correct 80 ms 21364 KB ok, correct split
10 Correct 62 ms 23348 KB ok, correct split
11 Correct 69 ms 23280 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11972 KB ok, correct split
2 Correct 6 ms 11988 KB ok, correct split
3 Correct 7 ms 11988 KB ok, correct split
4 Correct 113 ms 21948 KB ok, correct split
5 Correct 63 ms 18796 KB ok, correct split
6 Correct 65 ms 23372 KB ok, correct split
7 Correct 67 ms 21696 KB ok, correct split
8 Correct 91 ms 20996 KB ok, correct split
9 Correct 76 ms 18744 KB ok, correct split
10 Incorrect 52 ms 19104 KB invalid split: #1=1, #2=1, #3=99997
11 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 65 ms 18716 KB ok, correct split
3 Correct 29 ms 14676 KB ok, correct split
4 Incorrect 7 ms 11988 KB invalid split: #1=16, #2=16, #3=34
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Incorrect 6 ms 11988 KB invalid split: #1=2, #2=1, #3=3
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 6 ms 11988 KB ok, correct split
3 Correct 6 ms 12016 KB ok, correct split
4 Correct 6 ms 11988 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 6 ms 11988 KB ok, correct split
7 Correct 74 ms 23108 KB ok, correct split
8 Correct 65 ms 21744 KB ok, correct split
9 Correct 80 ms 21364 KB ok, correct split
10 Correct 62 ms 23348 KB ok, correct split
11 Correct 69 ms 23280 KB ok, correct split
12 Correct 9 ms 11972 KB ok, correct split
13 Correct 6 ms 11988 KB ok, correct split
14 Correct 7 ms 11988 KB ok, correct split
15 Correct 113 ms 21948 KB ok, correct split
16 Correct 63 ms 18796 KB ok, correct split
17 Correct 65 ms 23372 KB ok, correct split
18 Correct 67 ms 21696 KB ok, correct split
19 Correct 91 ms 20996 KB ok, correct split
20 Correct 76 ms 18744 KB ok, correct split
21 Incorrect 52 ms 19104 KB invalid split: #1=1, #2=1, #3=99997
22 Halted 0 ms 0 KB -