oj.uz

Submission #591080

# Submission time Handle Problem Language Result Execution time Memory
591080 2022-07-06T20:16:34 Z almothana05 Split the Attractions (IOI19_split) C++14
18 / 100
 90 ms 24132 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];
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;
		}
	}
	if(sub == gru[0].first + gru[1].first + gru[2].first ){
		return 0;
	}
	if(sub >= gru[0].first && sub < maxi){
		maxi = sub;
		pl = x;
	}
	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(kind != f[x] && vis[kind] == 0){
			dfs1(kind , ins);
		}
	}

}
vector<int> find_split(int menge, int a, int b, int c, vector<int> p, vector<int> q) {
	int root;
	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 i = 0 ; i < menge ; i++){
		vis[i] = 0;
	}
	if(maxi == mod){
		return vis;
	}
	re = gru[0].first;
	dfs1( pl , gru[0].second );
	re = gru[1].first;
	dfs1(root , gru[1].second);
	if(re > 0){
		assert(re != 100000 - 78160);
		assert(maxi <= 78160);
		for(int i = 0 ; i < menge ; i++){
			vis[i] =0;
		}
		return vis;
	}
	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:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  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:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0 ; i < p.size() ; i++){
      |                  ~~^~~~~~~~~~
split.cpp:64:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |  dfs(root);
      |  ~~~^~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11964 KB ok, correct split
2 Correct 7 ms 11988 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 7 ms 11988 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 6 ms 12060 KB ok, correct split
7 Correct 75 ms 23848 KB ok, correct split
8 Correct 69 ms 22048 KB ok, correct split
9 Correct 66 ms 21408 KB ok, correct split
10 Correct 60 ms 24092 KB ok, correct split
11 Correct 68 ms 24076 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11964 KB ok, correct split
2 Correct 7 ms 11944 KB ok, correct split
3 Correct 8 ms 11988 KB ok, correct split
4 Correct 78 ms 21792 KB ok, correct split
5 Correct 58 ms 18016 KB ok, correct split
6 Correct 61 ms 24132 KB ok, correct split
7 Correct 68 ms 21828 KB ok, correct split
8 Correct 90 ms 20164 KB ok, correct split
9 Correct 61 ms 17948 KB ok, correct split
10 Correct 49 ms 18292 KB ok, correct split
11 Correct 51 ms 18240 KB ok, correct split
12 Correct 47 ms 18304 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 Incorrect 57 ms 17940 KB jury found a solution, contestant did not
3 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 Correct 5 ms 11988 KB ok, no valid answer
3 Correct 6 ms 11988 KB ok, correct split
4 Incorrect 8 ms 11988 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11964 KB ok, correct split
2 Correct 7 ms 11988 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 7 ms 11988 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 6 ms 12060 KB ok, correct split
7 Correct 75 ms 23848 KB ok, correct split
8 Correct 69 ms 22048 KB ok, correct split
9 Correct 66 ms 21408 KB ok, correct split
10 Correct 60 ms 24092 KB ok, correct split
11 Correct 68 ms 24076 KB ok, correct split
12 Correct 6 ms 11964 KB ok, correct split
13 Correct 7 ms 11944 KB ok, correct split
14 Correct 8 ms 11988 KB ok, correct split
15 Correct 78 ms 21792 KB ok, correct split
16 Correct 58 ms 18016 KB ok, correct split
17 Correct 61 ms 24132 KB ok, correct split
18 Correct 68 ms 21828 KB ok, correct split
19 Correct 90 ms 20164 KB ok, correct split
20 Correct 61 ms 17948 KB ok, correct split
21 Correct 49 ms 18292 KB ok, correct split
22 Correct 51 ms 18240 KB ok, correct split
23 Correct 47 ms 18304 KB ok, correct split
24 Correct 6 ms 11988 KB ok, correct split
25 Incorrect 57 ms 17940 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -