oj.uz

답안 #591087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591087 2022-07-06T20:25:38 Z almothana05 Split the Attractions (IOI19_split) C++14
18 / 100
 103 ms 35604 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 7 ms 11964 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 6 ms 11944 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 6 ms 11988 KB ok, correct split
7 Correct 69 ms 23772 KB ok, correct split
8 Correct 72 ms 21988 KB ok, correct split
9 Correct 71 ms 21448 KB ok, correct split
10 Correct 74 ms 24224 KB ok, correct split
11 Correct 99 ms 24156 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 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 76 ms 21796 KB ok, correct split
5 Correct 59 ms 17984 KB ok, correct split
6 Correct 86 ms 24060 KB ok, correct split
7 Correct 75 ms 21792 KB ok, correct split
8 Correct 103 ms 20264 KB ok, correct split
9 Correct 75 ms 17936 KB ok, correct split
10 Correct 48 ms 18268 KB ok, correct split
11 Correct 47 ms 18328 KB ok, correct split
12 Correct 47 ms 18208 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 11988 KB ok, correct split
2 Runtime error 74 ms 35604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 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 15 ms 24244 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB ok, correct split
2 Correct 7 ms 11964 KB ok, correct split
3 Correct 6 ms 11988 KB ok, correct split
4 Correct 6 ms 11944 KB ok, correct split
5 Correct 6 ms 11988 KB ok, correct split
6 Correct 6 ms 11988 KB ok, correct split
7 Correct 69 ms 23772 KB ok, correct split
8 Correct 72 ms 21988 KB ok, correct split
9 Correct 71 ms 21448 KB ok, correct split
10 Correct 74 ms 24224 KB ok, correct split
11 Correct 99 ms 24156 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 76 ms 21796 KB ok, correct split
16 Correct 59 ms 17984 KB ok, correct split
17 Correct 86 ms 24060 KB ok, correct split
18 Correct 75 ms 21792 KB ok, correct split
19 Correct 103 ms 20264 KB ok, correct split
20 Correct 75 ms 17936 KB ok, correct split
21 Correct 48 ms 18268 KB ok, correct split
22 Correct 47 ms 18328 KB ok, correct split
23 Correct 47 ms 18208 KB ok, correct split
24 Correct 9 ms 11988 KB ok, correct split
25 Runtime error 74 ms 35604 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -