oj.uz

Submission #143630

# Submission time Handle Problem Language Result Execution time Memory
143630 2019-08-14T18:48:00 Z muradeyn Split the Attractions (IOI19_split) C++14
0 / 100
 134 ms 13688 KB 
#include "split.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxx = 200000;

int N , pos = -1 , par , cent;
int dp[maxx];

vector< pair<int,int> >spl;

vector<int>adj[maxx];

void dfs(int s,int p) {
    dp[s] = 1;
    bool f = true;
    for (int to : adj[s]) {
        if (to == p)continue;
        dfs(to , s);
        if (dp[to] >= spl[0].F) {
            if (pos == -1)pos = to , par = s;
            else if (dp[pos] > dp[to])pos = to , par = s;
        }
        f &= (dp[to] <= N / 2);
        dp[s] += dp[to];
    }
    f &= (N - dp[s] <= N / 2);
    if (f)cent = s;
}

vector<int>res;

int cnt = 0;

void label(int s,int p,int need,int mark) {
    cnt++;
    res[s] = mark;
    if (cnt == need)return;
    for (int to : adj[s]) {
        if (to == p || to == pos)continue;
        label(to , s , need , mark);
        if (cnt == need)return;
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n;
	res.resize(n , 0);
	spl.push_back({a , 1});
	spl.push_back({b , 2});
	spl.push_back({c , 3});
	sort(spl.begin(),spl.end());
	int m = p.size();
	if (n != m + 1)return res;
	for (int i = 0;i<m;i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
	}
	dfs(1 , -1);
	int rt = cent;
	dfs(rt , -1);
	if (pos == -1)return res;
	//if (n - dp[pos] < spl[1].F)return res;
	label(pos , par , spl[0].F , spl[0].S);
	cnt = 0;
	label(rt , -1 , spl[1].F , spl[1].S);
	for (int i = 0;i<n;i++)
        if (res[i] == 0)res[i] = spl[2].S;
    return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Incorrect 6 ms 4984 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Incorrect 6 ms 4984 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 94 ms 11052 KB ok, correct split
3 Correct 35 ms 7416 KB ok, correct split
4 Correct 9 ms 4984 KB ok, correct split
5 Correct 111 ms 13432 KB ok, correct split
6 Incorrect 134 ms 13688 KB invalid split: #1=12500, #2=35000, #3=52500
7 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Incorrect 6 ms 4984 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -