oj.uz

Submission #169929

# Submission time Handle Problem Language Result Execution time Memory
169929 2019-12-23T09:43:04 Z socho Split the Attractions (IOI19_split) C++14
0 / 100
 1078 ms 1048580 KB 
#include "bits/stdc++.h"
#include "split.h"
using namespace std;

int N;
const int MXN = 100005;
int stsize[MXN];
vector<int> adj[MXN];
int parent[MXN];
bool blocked[MXN];

int dfs_st(int node, int last) {
	int sz = 1;
	parent[node] = last;
	for (int i=0; i<adj[node].size(); i++) {
		int ot = adj[node][i];
		if (ot == last) continue;
		sz += dfs_st(ot, node);
	}
	return stsize[node] = sz;
}

int dfs_ce(int node, int last) {
	// cout << " > " << node << ' ' << stsize[node] << endl;
	for (int i=0; i<adj[node].size(); i++) {
		int ot = adj[node][i];
		if (ot == last) continue;
		if (stsize[ot] * 2 > N) return dfs_ce(ot, node);
	}
	return node;
}

int get_centroid() {
	dfs_st(0, -1);
	return dfs_ce(0, -1);
}

int limit = 0;
int taken = 0;
vector<int> picked;

void getst(int node) {
	if (taken >= limit) return;
	picked.push_back(node);
	blocked[node] = true;
	taken++;
	for (int i=0; i<adj[node].size(); i++) {
		if (adj[node][i] == parent[i]) continue;
		getst(adj[node][i]);
	}
}

vector<int> took;

void travel(int node, int last) {
	if (taken >= limit) return;
	took.push_back(node);
	blocked[node] = true;
	taken++;
	for (int i=0; i<adj[node].size(); i++) {
		int ot = adj[node][i];
		if (ot == last) continue;
		if (blocked[ot]) continue;
		travel(ot, node);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	
	N = n;
	for (int i=0; i<p.size(); i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	
	int cen = get_centroid();
	dfs_st(cen, -1);
	
	int vs[3] = {a, b, c};
	sort(vs, vs+3);
	int smallest = vs[0];
	
	int lowlabel, midlabel, highlabel;
	if (smallest == a) {
		lowlabel = 1;
		if (b > c) {
			midlabel = 3;
			highlabel = 2;
		}
		else {
			midlabel = 2;
			highlabel = 3;
		}
	}
	else if (smallest == b) {
		lowlabel = 2;
		if (a > c) {
			midlabel = 3;
			highlabel = 1;
		}
		else {
			midlabel = 1;
			highlabel = 3;
		}
	}
	else {
		lowlabel = 3;
		if (a > b) {
			midlabel = 2;
			highlabel = 1;
		}
		else {
			midlabel = 1;
			highlabel = 2;
		}
	}
	
	int where = cen;
	
	for (int i=0; i<n; i++) {
		if (stsize[i] >= smallest) {
			if (stsize[i] <= stsize[where]) {
				where = i;
			}
		}
	}
	
	int take = n - stsize[where];
	
	if (vs[1] > take) {
		vector<int> res;
		for (int i=0; i<n; i++) res.push_back(0);
		return res;
	}
	
	vector<int> res(n, 0);
	
	limit = smallest;
	taken = 0;
	memset(blocked, 0, sizeof blocked);
	getst(where);
	
	for (int i=0; i<picked.size(); i++) {
		res[picked[i]] = lowlabel;
	}
	
	limit = vs[1];
	taken = 0;
	travel(parent[where], where);
	
	for (int i=0; i<took.size(); i++) {
		res[took[i]] = midlabel;
	}
	
	for (int i=0; i<n; i++) {
		if (res[i] == 0) res[i] = highlabel;
	}
	
	return res;
}

Compilation message

split.cpp: In function 'int dfs_st(int, int)':
split.cpp:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'int dfs_ce(int, int)':
split.cpp:25:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void getst(int)':
split.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void travel(int, int)':
split.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<p.size(); i++) {
                ~^~~~~~~~~
split.cpp:143:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<picked.size(); i++) {
                ~^~~~~~~~~~~~~~
split.cpp:151:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<took.size(); i++) {
                ~^~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB ok, correct split
2 Runtime error 1078 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB ok, correct split
2 Runtime error 930 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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB ok, correct split
2 Incorrect 87 ms 11080 KB invalid split: #1=3, #2=40000, #3=59997
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 907 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB ok, correct split
2 Runtime error 1078 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -