oj.uz

Submission #591079

# Submission time Handle Problem Language Result Execution time Memory
591079 2022-07-06T20:12:29 Z almothana05 Split the Attractions (IOI19_split) C++14
18 / 100
 92 ms 35656 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(maxi <= 78159);
		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 11988 KB ok, correct split
2 Correct 6 ms 11988 KB ok, correct split
3 Correct 7 ms 11988 KB ok, correct split
4 Correct 7 ms 11988 KB ok, correct split
5 Correct 7 ms 11988 KB ok, correct split
6 Correct 7 ms 11988 KB ok, correct split
7 Correct 79 ms 23784 KB ok, correct split
8 Correct 63 ms 22064 KB ok, correct split
9 Correct 68 ms 21480 KB ok, correct split
10 Correct 65 ms 24168 KB ok, correct split
11 Correct 75 ms 24076 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 7 ms 11932 KB ok, correct split
3 Correct 6 ms 12004 KB ok, correct split
4 Correct 79 ms 21832 KB ok, correct split
5 Correct 89 ms 17948 KB ok, correct split
6 Correct 84 ms 24180 KB ok, correct split
7 Correct 68 ms 21896 KB ok, correct split
8 Correct 92 ms 20260 KB ok, correct split
9 Correct 62 ms 17860 KB ok, correct split
10 Correct 48 ms 18296 KB ok, correct split
11 Correct 46 ms 18244 KB ok, correct split
12 Correct 48 ms 18244 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB ok, correct split
2 Runtime error 84 ms 35656 KB Execution killed with signal 6
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 6 ms 12000 KB ok, no valid answer
3 Correct 7 ms 11988 KB ok, correct split
4 Incorrect 7 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 11988 KB ok, correct split
2 Correct 6 ms 11988 KB ok, correct split
3 Correct 7 ms 11988 KB ok, correct split
4 Correct 7 ms 11988 KB ok, correct split
5 Correct 7 ms 11988 KB ok, correct split
6 Correct 7 ms 11988 KB ok, correct split
7 Correct 79 ms 23784 KB ok, correct split
8 Correct 63 ms 22064 KB ok, correct split
9 Correct 68 ms 21480 KB ok, correct split
10 Correct 65 ms 24168 KB ok, correct split
11 Correct 75 ms 24076 KB ok, correct split
12 Correct 6 ms 11988 KB ok, correct split
13 Correct 7 ms 11932 KB ok, correct split
14 Correct 6 ms 12004 KB ok, correct split
15 Correct 79 ms 21832 KB ok, correct split
16 Correct 89 ms 17948 KB ok, correct split
17 Correct 84 ms 24180 KB ok, correct split
18 Correct 68 ms 21896 KB ok, correct split
19 Correct 92 ms 20260 KB ok, correct split
20 Correct 62 ms 17860 KB ok, correct split
21 Correct 48 ms 18296 KB ok, correct split
22 Correct 46 ms 18244 KB ok, correct split
23 Correct 48 ms 18244 KB ok, correct split
24 Correct 8 ms 11988 KB ok, correct split
25 Runtime error 84 ms 35656 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -