oj.uz

Submission #591088

# Submission time Handle Problem Language Result Execution time Memory
591088 2022-07-06T20:26:07 Z almothana05 Split the Attractions (IOI19_split) C++14
18 / 100
 98 ms 24164 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 >= gru[1].first && gru[1].first > gru[0].first);
		// 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 6 ms 11988 KB ok, correct split
4 Correct 7 ms 11988 KB ok, correct split
5 Correct 7 ms 11940 KB ok, correct split
6 Correct 7 ms 11988 KB ok, correct split
7 Correct 75 ms 23812 KB ok, correct split
8 Correct 62 ms 21964 KB ok, correct split
9 Correct 91 ms 21420 KB ok, correct split
10 Correct 78 ms 24164 KB ok, correct split
11 Correct 70 ms 24084 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 6 ms 11988 KB ok, correct split
3 Correct 6 ms 12028 KB ok, correct split
4 Correct 85 ms 21824 KB ok, correct split
5 Correct 74 ms 17932 KB ok, correct split
6 Correct 64 ms 24132 KB ok, correct split
7 Correct 70 ms 21832 KB ok, correct split
8 Correct 98 ms 20184 KB ok, correct split
9 Correct 61 ms 17868 KB ok, correct split
10 Correct 57 ms 18224 KB ok, correct split
11 Correct 61 ms 18268 KB ok, correct split
12 Correct 51 ms 18188 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 58 ms 18016 KB invalid split: #1=20000, #2=21840, #3=58160
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 11976 KB ok, no valid answer
3 Correct 6 ms 11984 KB ok, correct split
4 Incorrect 6 ms 11980 KB invalid split: #1=1, #2=3, #3=7
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 6 ms 11988 KB ok, correct split
4 Correct 7 ms 11988 KB ok, correct split
5 Correct 7 ms 11940 KB ok, correct split
6 Correct 7 ms 11988 KB ok, correct split
7 Correct 75 ms 23812 KB ok, correct split
8 Correct 62 ms 21964 KB ok, correct split
9 Correct 91 ms 21420 KB ok, correct split
10 Correct 78 ms 24164 KB ok, correct split
11 Correct 70 ms 24084 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 12028 KB ok, correct split
15 Correct 85 ms 21824 KB ok, correct split
16 Correct 74 ms 17932 KB ok, correct split
17 Correct 64 ms 24132 KB ok, correct split
18 Correct 70 ms 21832 KB ok, correct split
19 Correct 98 ms 20184 KB ok, correct split
20 Correct 61 ms 17868 KB ok, correct split
21 Correct 57 ms 18224 KB ok, correct split
22 Correct 61 ms 18268 KB ok, correct split
23 Correct 51 ms 18188 KB ok, correct split
24 Correct 6 ms 11988 KB ok, correct split
25 Incorrect 58 ms 18016 KB invalid split: #1=20000, #2=21840, #3=58160
26 Halted 0 ms 0 KB -