oj.uz

Submission #591085

# Submission time Handle Problem Language Result Execution time Memory
591085 2022-07-06T20:21:43 Z almothana05 Split the Attractions (IOI19_split) C++14
18 / 100
 100 ms 35540 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(gru[2].first == 58160);
		assert(menge == 100000);
		// 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 8 ms 11988 KB ok, correct split
2 Correct 6 ms 11940 KB ok, correct split
3 Correct 6 ms 12040 KB ok, correct split
4 Correct 6 ms 11928 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 7 ms 11988 KB ok, correct split
7 Correct 74 ms 23868 KB ok, correct split
8 Correct 69 ms 22036 KB ok, correct split
9 Correct 83 ms 21396 KB ok, correct split
10 Correct 65 ms 24092 KB ok, correct split
11 Correct 67 ms 24056 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB ok, correct split
2 Correct 6 ms 11988 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 80 ms 21788 KB ok, correct split
5 Correct 61 ms 17980 KB ok, correct split
6 Correct 64 ms 24152 KB ok, correct split
7 Correct 64 ms 21900 KB ok, correct split
8 Correct 100 ms 20164 KB ok, correct split
9 Correct 58 ms 17860 KB ok, correct split
10 Correct 47 ms 18324 KB ok, correct split
11 Correct 46 ms 18204 KB ok, correct split
12 Correct 46 ms 18204 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12008 KB ok, correct split
2 Runtime error 61 ms 35540 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 11924 KB ok, correct split
2 Correct 6 ms 11988 KB ok, no valid answer
3 Correct 7 ms 11988 KB ok, correct split
4 Runtime error 15 ms 24188 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB ok, correct split
2 Correct 6 ms 11940 KB ok, correct split
3 Correct 6 ms 12040 KB ok, correct split
4 Correct 6 ms 11928 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 7 ms 11988 KB ok, correct split
7 Correct 74 ms 23868 KB ok, correct split
8 Correct 69 ms 22036 KB ok, correct split
9 Correct 83 ms 21396 KB ok, correct split
10 Correct 65 ms 24092 KB ok, correct split
11 Correct 67 ms 24056 KB ok, correct split
12 Correct 8 ms 11988 KB ok, correct split
13 Correct 6 ms 11988 KB ok, correct split
14 Correct 6 ms 11988 KB ok, correct split
15 Correct 80 ms 21788 KB ok, correct split
16 Correct 61 ms 17980 KB ok, correct split
17 Correct 64 ms 24152 KB ok, correct split
18 Correct 64 ms 21900 KB ok, correct split
19 Correct 100 ms 20164 KB ok, correct split
20 Correct 58 ms 17860 KB ok, correct split
21 Correct 47 ms 18324 KB ok, correct split
22 Correct 46 ms 18204 KB ok, correct split
23 Correct 46 ms 18204 KB ok, correct split
24 Correct 6 ms 12008 KB ok, correct split
25 Runtime error 61 ms 35540 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -