oj.uz

Submission #591113

# Submission time Handle Problem Language Result Execution time Memory
591113 2022-07-06T21:37:44 Z almothana05 Split the Attractions (IOI19_split) C++14
18 / 100
 113 ms 28688 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:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i = 0 ; i< gr[x].size() ; i ++){
      |                  ~^~~~~~~~~~~~~~
split.cpp: In function 'void dfs1(int, int)':
split.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  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:50:20: 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 < p.size() ; i++){
      |                  ~~^~~~~~~~~~
split.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0 ; i < gr[x].size() ; i++ ){
      |                   ~~^~~~~~~~~~~~~~
split.cpp:60:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |  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 12072 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 104 ms 22776 KB ok, correct split
8 Correct 76 ms 21388 KB ok, correct split
9 Correct 76 ms 20888 KB ok, correct split
10 Correct 59 ms 22980 KB ok, correct split
11 Correct 113 ms 22880 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB ok, correct split
2 Correct 6 ms 11944 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 80 ms 21468 KB ok, correct split
5 Correct 88 ms 18308 KB ok, correct split
6 Correct 62 ms 22996 KB ok, correct split
7 Correct 69 ms 21184 KB ok, correct split
8 Correct 100 ms 20560 KB ok, correct split
9 Correct 63 ms 18244 KB ok, correct split
10 Correct 46 ms 18608 KB ok, correct split
11 Correct 48 ms 18680 KB ok, correct split
12 Correct 49 ms 18636 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 60 ms 18320 KB ok, correct split
3 Correct 25 ms 14544 KB ok, correct split
4 Correct 6 ms 11988 KB ok, correct split
5 Correct 71 ms 21040 KB ok, correct split
6 Correct 76 ms 20804 KB ok, correct split
7 Correct 71 ms 20804 KB ok, correct split
8 Correct 73 ms 21572 KB ok, correct split
9 Correct 72 ms 20876 KB ok, correct split
10 Runtime error 28 ms 28688 KB Execution killed with signal 6
11 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 Runtime error 14 ms 24280 KB Execution killed with signal 6
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 12072 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 104 ms 22776 KB ok, correct split
8 Correct 76 ms 21388 KB ok, correct split
9 Correct 76 ms 20888 KB ok, correct split
10 Correct 59 ms 22980 KB ok, correct split
11 Correct 113 ms 22880 KB ok, correct split
12 Correct 5 ms 11988 KB ok, correct split
13 Correct 6 ms 11944 KB ok, correct split
14 Correct 6 ms 11988 KB ok, correct split
15 Correct 80 ms 21468 KB ok, correct split
16 Correct 88 ms 18308 KB ok, correct split
17 Correct 62 ms 22996 KB ok, correct split
18 Correct 69 ms 21184 KB ok, correct split
19 Correct 100 ms 20560 KB ok, correct split
20 Correct 63 ms 18244 KB ok, correct split
21 Correct 46 ms 18608 KB ok, correct split
22 Correct 48 ms 18680 KB ok, correct split
23 Correct 49 ms 18636 KB ok, correct split
24 Correct 6 ms 11988 KB ok, correct split
25 Correct 60 ms 18320 KB ok, correct split
26 Correct 25 ms 14544 KB ok, correct split
27 Correct 6 ms 11988 KB ok, correct split
28 Correct 71 ms 21040 KB ok, correct split
29 Correct 76 ms 20804 KB ok, correct split
30 Correct 71 ms 20804 KB ok, correct split
31 Correct 73 ms 21572 KB ok, correct split
32 Correct 72 ms 20876 KB ok, correct split
33 Runtime error 28 ms 28688 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -