oj.uz

답안 #245051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245051 2020-07-05T11:28:32 Z crossing0ver Split the Attractions (IOI19_split) C++17
0 / 100
 769 ms 1048580 KB 
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#ifndef local
#include "split.h"
#endif
using namespace std;
const int MXN = 1e5 +5; 
int n,a,b,c,m;
vector<int> adj[MXN];
vi case1() {
	vector<bool> vis(n);
	vis[0] = 1;
	queue<int> q;
	set<int> sec;
	int cnt = b;
	q.push(0);
	while(!q.empty() && cnt) {
		cnt--;
		int v = q.front();
		sec.insert(v);
		q.pop();
		for (int i :adj[v]) {
			if (!vis[i]) {
				vis[i] = 1;
				q.push(i);
			}
		}
	}
	vector<int> ans(n);
	for (int i : sec) ans[i] = 2;
	for (int i = 0,flag = 0; i < n; i++) {
		if (sec.count(i)) continue;
		if (flag == 0) flag = 1, ans[i] = 1;
		else ans[i] = 3;
	} 
	return ans;
}

int sz[MXN],flag,X[4],mn;
set<int> ans[4];
void dfs(int v,int p,int type) {
	if (type == 1 && X[flag]) {
		X[flag]--;
		ans[flag].insert(v);
	}
	sz[v] = 1;
	for (int i : adj[v]) {
		if (i == p) continue;
		dfs(i,v,type);
		sz[v] += sz[i];
	}
	if (flag) return;
	if (sz[v] >= a && n - sz[v] >= min(b,c)) {
		flag = 1;
		if (n - sz[v] >= b) mn = 2;
		else mn = 3;
	}
	else if (sz[v] >= b && n - sz[v] >= min(a,c)) {
		flag = 2;
		if (n - sz[v] >= a) mn = 1;
		else mn = 3;
	}
	else if (sz[v] >= c && n - sz[v] >= min(a,b)) {
		flag = 3;
		if (n - sz[v] >= a) mn = 1;
		else mn = 2;
	}
	else return;
	dfs(v,p,1);
	flag = mn;
	if (p != -1)
	dfs(p,v,1);
}
vi case2() {
	int cnt = 0;
	vi v,vis(n);
	int cur = 0;
	while(cnt != n) {
		cnt++;
		vis[cur] = 1;
		v.push_back(cur);
		for (int i : adj[cur]) {
			if (vis[i]) continue;
			cur = i;
			break;
		}
	}
	vi ans(n);
	if (v.size() != n) {
		while(true){
			
		}
	}
	for (int i = 0; i < a;i++) ans[v[i]] = 1;
	for (int i = a; i < a + b; i++) ans[v[i]] = 2;
	for (int i = a+b; i < n; i++) ans[v[i]] = 3;
	return ans;
}
int P[MXN],seen[MXN];
vi e[MXN],graph[MXN];
void SDS(int v) {
	seen[v] = 1;
	for (int i : graph[v]) {
		if (seen[i]) continue;
		e[v].pb(i);
		e[i].pb(v);
		SDS(i);
	}
}
vector<int> find_split(int n1, int a1, int b1, int c1, vector<int> p, vector<int> q) {
	n = n1,a = a1,b=b1,c=c1;
	X[1] = a,X[2] = b, X[3] = c;
	m = p.size();
	for (int i = 0;i < m; i++) {
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	for (int i = 0; i < n; i++)
		graph[i] = adj[i];
	for (int i = 0; i < n; i++) {
		memset(seen,0,sizeof seen);
		SDS(i);
		for (int j = 1; j < 4;j++) ans[i].clear();
		X[1] = a,X[2] = b, X[3] = c;
		dfs(i,-1,0);
		if (flag == 0) continue;
		vector<int> res(n),vis(n);
	for (int j = 1; j <= 3; j++)
	for (int i : ans[j]) res[i] = j,vis[i] = 1;
	int id;
	for (int i = 1; i <= 3; i++) if (ans[i].empty()) id = i;
	for (int i = 0; i < n; i++) if (!vis[i]) res[i] = id;
	return res;
	}
	return vi(n,0);

}

Compilation message

split.cpp: In function 'std::vector<int> case2()':
split.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (v.size() != n) {
      ~~~~~~~~~^~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7808 KB ok, correct split
2 Runtime error 769 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7808 KB ok, correct split
2 Runtime error 695 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 7808 KB ok, correct split
2 Correct 212 ms 22904 KB ok, correct split
3 Correct 67 ms 12792 KB ok, correct split
4 Correct 10 ms 7808 KB ok, correct split
5 Correct 241 ms 25080 KB ok, correct split
6 Correct 206 ms 24824 KB ok, correct split
7 Correct 212 ms 25592 KB ok, correct split
8 Correct 257 ms 25848 KB ok, correct split
9 Correct 228 ms 25336 KB ok, correct split
10 Runtime error 92 ms 26360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 703 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7808 KB ok, correct split
2 Runtime error 769 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -