Submission #591084

# Submission time Handle Problem Language Result Execution time Memory
591084 2022-07-06T20:21:03 Z almothana05 Split the Attractions (IOI19_split) C++14
18 / 100
106 ms 24196 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[0].first == 20000);
		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 11988 KB ok, correct split
2 Correct 8 ms 11988 KB ok, correct split
3 Correct 8 ms 12000 KB ok, correct split
4 Correct 6 ms 11988 KB ok, correct split
5 Correct 6 ms 12036 KB ok, correct split
6 Correct 7 ms 12016 KB ok, correct split
7 Correct 71 ms 23864 KB ok, correct split
8 Correct 58 ms 22060 KB ok, correct split
9 Correct 82 ms 21572 KB ok, correct split
10 Correct 71 ms 24148 KB ok, correct split
11 Correct 70 ms 24136 KB ok, correct split
# 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 11988 KB ok, correct split
4 Correct 77 ms 21800 KB ok, correct split
5 Correct 70 ms 17988 KB ok, correct split
6 Correct 59 ms 24112 KB ok, correct split
7 Correct 69 ms 21892 KB ok, correct split
8 Correct 106 ms 20264 KB ok, correct split
9 Correct 66 ms 17860 KB ok, correct split
10 Correct 45 ms 18212 KB ok, correct split
11 Correct 46 ms 18204 KB ok, correct split
12 Correct 48 ms 18336 KB ok, correct split
# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB ok, correct split
2 Incorrect 69 ms 18028 KB invalid split: #1=20000, #2=21840, #3=58160
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 17 ms 24196 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 8 ms 11988 KB ok, correct split
3 Correct 8 ms 12000 KB ok, correct split
4 Correct 6 ms 11988 KB ok, correct split
5 Correct 6 ms 12036 KB ok, correct split
6 Correct 7 ms 12016 KB ok, correct split
7 Correct 71 ms 23864 KB ok, correct split
8 Correct 58 ms 22060 KB ok, correct split
9 Correct 82 ms 21572 KB ok, correct split
10 Correct 71 ms 24148 KB ok, correct split
11 Correct 70 ms 24136 KB ok, correct split
12 Correct 6 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 77 ms 21800 KB ok, correct split
16 Correct 70 ms 17988 KB ok, correct split
17 Correct 59 ms 24112 KB ok, correct split
18 Correct 69 ms 21892 KB ok, correct split
19 Correct 106 ms 20264 KB ok, correct split
20 Correct 66 ms 17860 KB ok, correct split
21 Correct 45 ms 18212 KB ok, correct split
22 Correct 46 ms 18204 KB ok, correct split
23 Correct 48 ms 18336 KB ok, correct split
24 Correct 8 ms 11988 KB ok, correct split
25 Incorrect 69 ms 18028 KB invalid split: #1=20000, #2=21840, #3=58160
26 Halted 0 ms 0 KB -