oj.uz

답안 #591107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591107 2022-07-06T21:31:11 Z almothana05 Split the Attractions (IOI19_split) C++14
7 / 100
 105 ms 23372 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] ,pl2 , menge;
int unt[300000] , ob[300000];
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;
		}
	}
	unt[x] = sub;
	ob[x] = menge - unt[x] + 1;
	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(vis[kind] == 0){
			dfs1(kind , ins);
		}
	}

}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int root;
	menge = n;
	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 x = 0 ; x < menge ; x++){
		vis[x] = 0;
		for(int i = 0 ; i < gr[x].size() ; i++ ){
			int kind = gr[x][i];
			if(kind == f[x]){
				if(unt[x] > gru[0].first && maxi > unt[x]){
					maxi = unt[x];
					pl = x;
					pl2 = kind;
				}
			}
			else{
				if(menge - unt[kind] > gru[0].first && maxi > menge - unt[kind]){
					maxi = menge - unt[kind];
					pl = x;
					pl2 = kind;
				}
			}
		}
	}
	if(maxi == mod){
		return vis;
	}
	vis[pl] = gru[0].second;
	re = gru[1].first;
	dfs1( pl2 , 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;
	}
	re = gru[0].first;
	dfs1(pl , gru[0].second);
	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:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0 ; i< gr[x].size() ; i ++){
      |                  ~^~~~~~~~~~~~~~
split.cpp: In function 'void dfs1(int, int)':
split.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  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:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i = 0 ; i < p.size() ; i++){
      |                  ~~^~~~~~~~~~
split.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int i = 0 ; i < gr[x].size() ; i++ ){
      |                   ~~^~~~~~~~~~~~~~
split.cpp:61:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |  dfs(root);
      |  ~~~^~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB ok, correct split
2 Correct 7 ms 11988 KB ok, correct split
3 Correct 7 ms 11988 KB ok, correct split
4 Correct 8 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 71 ms 23104 KB ok, correct split
8 Correct 71 ms 21700 KB ok, correct split
9 Correct 80 ms 21384 KB ok, correct split
10 Correct 67 ms 23372 KB ok, correct split
11 Correct 87 ms 23364 KB ok, correct split

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 105 ms 21856 KB ok, correct split
5 Correct 63 ms 18804 KB ok, correct split
6 Correct 73 ms 23320 KB ok, correct split
7 Correct 68 ms 21572 KB ok, correct split
8 Correct 95 ms 20936 KB ok, correct split
9 Correct 85 ms 18792 KB ok, correct split
10 Incorrect 59 ms 19012 KB jury found a solution, contestant did not
11 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12012 KB ok, correct split
2 Correct 64 ms 18804 KB ok, correct split
3 Correct 27 ms 15176 KB ok, correct split
4 Incorrect 7 ms 11988 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12068 KB ok, correct split
2 Correct 6 ms 12020 KB ok, no valid answer
3 Correct 6 ms 11988 KB ok, correct split
4 Incorrect 7 ms 11988 KB invalid split: #1=4, #2=1, #3=6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB ok, correct split
2 Correct 7 ms 11988 KB ok, correct split
3 Correct 7 ms 11988 KB ok, correct split
4 Correct 8 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 71 ms 23104 KB ok, correct split
8 Correct 71 ms 21700 KB ok, correct split
9 Correct 80 ms 21384 KB ok, correct split
10 Correct 67 ms 23372 KB ok, correct split
11 Correct 87 ms 23364 KB ok, correct split
12 Correct 7 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 105 ms 21856 KB ok, correct split
16 Correct 63 ms 18804 KB ok, correct split
17 Correct 73 ms 23320 KB ok, correct split
18 Correct 68 ms 21572 KB ok, correct split
19 Correct 95 ms 20936 KB ok, correct split
20 Correct 85 ms 18792 KB ok, correct split
21 Incorrect 59 ms 19012 KB jury found a solution, contestant did not
22 Halted 0 ms 0 KB -