oj.uz

Submission #161794

# Submission time Handle Problem Language Result Execution time Memory
161794 2019-11-04T12:21:25 Z andrew Split the Attractions (IOI19_split) C++17
40 / 100
 943 ms 1048576 KB 
#include <bits/stdc++.h>
#include "split.h"

#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>


using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;

vector <int> v[N];

int t[N], P[N];
bool f[N];

void dfs(int x, int pr){
    P[x] = pr;
    t[x] = 1;
    for(auto to : v[x])if(to != pr){
        dfs(to, x);
        t[x] += t[to];
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = p.size(), mx = 0;

    for(int i = 0; i < n; i++){
        v[i].clear();
        t[i] = 0;
    }

    for(int i = 0; i < m; i++){
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
        mx = max(mx, (int)v[p[i]].size());
        mx = max(mx, (int)v[q[i]].size());
    }

    vector <int> res(n);
    if(mx < 3){
        int F = 0, Last = 0;
        for(int i = 0; i < n; i++)if(v[i].size() == 1)F = i;
        int step = 1;
        vector <int> cnt(3);
        cnt[0] = a;
        cnt[1] = b;
        cnt[2] = c;
        for(int i = 0; i < n; i++){
            if(i){
                int New = 0;
                for(auto j : v[F])if(j != Last)New = j;
                Last = F;
                F = New;
            }
            while(!cnt[step - 1])step++;
            --cnt[step - 1];
            res[F] = step;
        }
        return res;
    }else if(a == 1){
        queue <int> q;
        int start = 0;
        q.push(start);
        vector <bool> f(n);
        f[start] = 1;

        while(!q.empty()){
            int x = q.front();
            q.pop();
            if(!b)break;
            b--;
            res[x] = 2;
            for(auto to : v[x])if(!f[to]){
                f[to] = 1;
                q.push(to);
            }
        }

        for(int i = 0; i < n; i++)if(res[i] == 0){res[i] = 1; break;}
        for(int i = 0; i < n; i++)if(res[i] == 0)res[i] = 3;
        return res;
    }else{
        int start = 0;
        for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i;
        vector <int> cnt(3);
        cnt[0] = a;
        cnt[1] = b;
        cnt[2] = c;
        vector <int> p(3);
        p[0] = 1;
        p[1] = 2;
        p[2] = 3;

        for(int i = 0; i < 3; i++)
            for(int j = i + 1; j < 3; j++)if(cnt[p[i] - 1] > cnt[p[j] - 1])swap(p[i], p[j]);

        dfs(start, -1);

        for(int i = 0; i < n; i++)if(t[i] >= cnt[p[1] - 1] && n - t[i] >= cnt[p[0] - 1]){
            queue <int> q;

            f[i] = 1;
            f[P[i]] = 1;

            res[P[i]] = p[0];
            cnt[p[0] - 1]--;

            q.push(P[i]);
            while(!q.empty()){
                int x = q.front();
                q.pop();
                res[x] = p[0];
                for(auto to : v[x])if(!f[to] && cnt[p[0] - 1]){
                    cnt[p[0] - 1]--;
                    f[to] = 1;
                    q.push(to);
                }
            }

            res[i] = p[1];
            cnt[p[1] - 1]--;

            q.push(i);
            while(!q.empty()){
                int x = q.front();
                q.pop();
                res[x] = p[1];
                for(auto to : v[x])if(!f[to] && cnt[p[1] - 1]){
                    cnt[p[1] - 1]--;
                    f[to] = 1;
                    q.push(to);
                }
            }
            for(auto &j : res)if(j == 0)j = p[2];
            return res;
        }

        swap(p[0], p[1]);

        for(int i = 0; i < n; i++)if(t[i] >= cnt[p[1] - 1] && n - t[i] >= cnt[p[0] - 1]){
            queue <int> q;

            f[i] = 1;
            f[P[i]] = 1;

            res[P[i]] = p[0];
            cnt[p[0] - 1]--;

            q.push(P[i]);
            while(!q.empty()){
                int x = q.front();
                q.pop();
                res[x] = p[0];
                for(auto to : v[x])if(!f[to] && cnt[p[0] - 1]){
                    cnt[p[0] - 1]--;
                    f[to] = 1;
                    q.push(to);
                }
            }

            res[i] = p[1];
            cnt[p[1] - 1]--;

            q.push(i);
            while(!q.empty()){
                int x = q.front();
                q.pop();
                res[x] = p[1];
                for(auto to : v[x])if(!f[to] && cnt[p[1] - 1]){
                    cnt[p[1] - 1]--;
                    f[to] = 1;
                    q.push(to);
                }
            }
            for(auto &j : res)if(j == 0)j = p[2];
            return res;
        }

        return res;
    }
	return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 4988 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 7 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 6 ms 4984 KB ok, correct split
7 Correct 80 ms 10588 KB ok, correct split
8 Correct 78 ms 10488 KB ok, correct split
9 Correct 87 ms 10488 KB ok, correct split
10 Correct 79 ms 10488 KB ok, correct split
11 Correct 83 ms 10512 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 10 ms 4984 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 99 ms 11740 KB ok, correct split
5 Correct 78 ms 10744 KB ok, correct split
6 Correct 81 ms 10460 KB ok, correct split
7 Correct 82 ms 10488 KB ok, correct split
8 Correct 133 ms 13068 KB ok, correct split
9 Correct 95 ms 10488 KB ok, correct split
10 Correct 63 ms 11248 KB ok, correct split
11 Correct 63 ms 11376 KB ok, correct split
12 Correct 67 ms 11248 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4988 KB ok, correct split
2 Correct 88 ms 11104 KB ok, correct split
3 Correct 35 ms 7928 KB ok, correct split
4 Correct 7 ms 5112 KB ok, correct split
5 Correct 102 ms 15096 KB ok, correct split
6 Correct 113 ms 15272 KB ok, correct split
7 Correct 115 ms 15096 KB ok, correct split
8 Correct 110 ms 15168 KB ok, correct split
9 Correct 125 ms 15224 KB ok, correct split
10 Correct 29 ms 7440 KB ok, no valid answer
11 Correct 44 ms 8568 KB ok, no valid answer
12 Correct 77 ms 12276 KB ok, no valid answer
13 Correct 79 ms 12280 KB ok, no valid answer
14 Correct 109 ms 12552 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 943 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 6 ms 4984 KB ok, correct split
2 Correct 6 ms 4988 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 7 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 6 ms 4984 KB ok, correct split
7 Correct 80 ms 10588 KB ok, correct split
8 Correct 78 ms 10488 KB ok, correct split
9 Correct 87 ms 10488 KB ok, correct split
10 Correct 79 ms 10488 KB ok, correct split
11 Correct 83 ms 10512 KB ok, correct split
12 Correct 6 ms 4984 KB ok, correct split
13 Correct 10 ms 4984 KB ok, correct split
14 Correct 6 ms 4984 KB ok, correct split
15 Correct 99 ms 11740 KB ok, correct split
16 Correct 78 ms 10744 KB ok, correct split
17 Correct 81 ms 10460 KB ok, correct split
18 Correct 82 ms 10488 KB ok, correct split
19 Correct 133 ms 13068 KB ok, correct split
20 Correct 95 ms 10488 KB ok, correct split
21 Correct 63 ms 11248 KB ok, correct split
22 Correct 63 ms 11376 KB ok, correct split
23 Correct 67 ms 11248 KB ok, correct split
24 Correct 6 ms 4988 KB ok, correct split
25 Correct 88 ms 11104 KB ok, correct split
26 Correct 35 ms 7928 KB ok, correct split
27 Correct 7 ms 5112 KB ok, correct split
28 Correct 102 ms 15096 KB ok, correct split
29 Correct 113 ms 15272 KB ok, correct split
30 Correct 115 ms 15096 KB ok, correct split
31 Correct 110 ms 15168 KB ok, correct split
32 Correct 125 ms 15224 KB ok, correct split
33 Correct 29 ms 7440 KB ok, no valid answer
34 Correct 44 ms 8568 KB ok, no valid answer
35 Correct 77 ms 12276 KB ok, no valid answer
36 Correct 79 ms 12280 KB ok, no valid answer
37 Correct 109 ms 12552 KB ok, no valid answer
38 Runtime error 943 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Halted 0 ms 0 KB -