Submission #591083

# Submission time Handle Problem Language Result Execution time Memory
591083 2022-07-06T20:19:21 Z almothana05 Split the Attractions (IOI19_split) C++14
18 / 100
98 ms 35548 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[1].first == 100000 - 78160);
		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);
      |  ~~~^~~~~~
# Verdict Execution time Memory Grader output
1 Correct 6 ms 11972 KB ok, correct split
2 Correct 6 ms 11988 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 6 ms 11964 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 6 ms 11988 KB ok, correct split
7 Correct 75 ms 23868 KB ok, correct split
8 Correct 86 ms 22020 KB ok, correct split
9 Correct 62 ms 21400 KB ok, correct split
10 Correct 68 ms 24132 KB ok, correct split
11 Correct 81 ms 24136 KB ok, correct split
# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 7 ms 11988 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 73 ms 21792 KB ok, correct split
5 Correct 61 ms 17988 KB ok, correct split
6 Correct 98 ms 24132 KB ok, correct split
7 Correct 92 ms 21896 KB ok, correct split
8 Correct 88 ms 20196 KB ok, correct split
9 Correct 68 ms 17988 KB ok, correct split
10 Correct 66 ms 18204 KB ok, correct split
11 Correct 66 ms 18200 KB ok, correct split
12 Correct 45 ms 18208 KB ok, correct split
# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Runtime error 54 ms 35548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 6 ms 11988 KB ok, no valid answer
3 Correct 6 ms 11988 KB ok, correct split
4 Runtime error 18 ms 24272 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 11972 KB ok, correct split
2 Correct 6 ms 11988 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 6 ms 11964 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 6 ms 11988 KB ok, correct split
7 Correct 75 ms 23868 KB ok, correct split
8 Correct 86 ms 22020 KB ok, correct split
9 Correct 62 ms 21400 KB ok, correct split
10 Correct 68 ms 24132 KB ok, correct split
11 Correct 81 ms 24136 KB ok, correct split
12 Correct 6 ms 11988 KB ok, correct split
13 Correct 7 ms 11988 KB ok, correct split
14 Correct 6 ms 11988 KB ok, correct split
15 Correct 73 ms 21792 KB ok, correct split
16 Correct 61 ms 17988 KB ok, correct split
17 Correct 98 ms 24132 KB ok, correct split
18 Correct 92 ms 21896 KB ok, correct split
19 Correct 88 ms 20196 KB ok, correct split
20 Correct 68 ms 17988 KB ok, correct split
21 Correct 66 ms 18204 KB ok, correct split
22 Correct 66 ms 18200 KB ok, correct split
23 Correct 45 ms 18208 KB ok, correct split
24 Correct 6 ms 11988 KB ok, correct split
25 Runtime error 54 ms 35548 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -