oj.uz

Submission #169930

# Submission time Handle Problem Language Result Execution time Memory
169930 2019-12-23T09:50:08 Z socho Split the Attractions (IOI19_split) C++14
0 / 100
 975 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;
		if (blocked[adj[node][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;
		}
	}
	
	// cout << "cent: " << cen << endl;
	// cout << lowlabel << ' ' << midlabel << ' ' << highlabel << endl;
	
	int where = cen;
	
	for (int i=0; i<n; i++) {
		if (stsize[i] >= smallest) {
			if (stsize[i] <= stsize[where]) {
				where = i;
			}
		}
	}
	
	// cout << "cancel: " << where << endl;
	
	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);
	
	// cout << "smallest: " << picked.size() << ' ' << limit << endl;
	for (int i=0; i<picked.size(); i++) {
		// cout << " > " << picked[i] << endl;
		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:61: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:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<p.size(); i++) {
                ~^~~~~~~~~
split.cpp:150:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<picked.size(); i++) {
                ~^~~~~~~~~~~~~~
split.cpp:159: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 2812 KB ok, correct split
2 Runtime error 891 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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB ok, correct split
2 Runtime error 906 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 2804 KB ok, correct split
2 Incorrect 91 ms 9308 KB invalid split: #1=19999, #2=40000, #3=40001
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 975 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

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