oj.uz

Submission #161792

# Submission time Handle Problem Language Result Execution time Memory
161792 2019-11-04T12:18:45 Z andrew Split the Attractions (IOI19_split) C++17
18 / 100
 954 ms 1048580 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[0] - 1] && n - t[i] >= cnt[p[1] - 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 4988 KB ok, correct split
2 Correct 7 ms 4984 KB ok, correct split
3 Correct 6 ms 4988 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 7 ms 4984 KB ok, correct split
7 Correct 102 ms 10616 KB ok, correct split
8 Correct 84 ms 10488 KB ok, correct split
9 Correct 86 ms 10616 KB ok, correct split
10 Correct 100 ms 11640 KB ok, correct split
11 Correct 94 ms 11640 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4988 KB ok, correct split
2 Correct 11 ms 4984 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 113 ms 11612 KB ok, correct split
5 Correct 74 ms 10628 KB ok, correct split
6 Correct 86 ms 10496 KB ok, correct split
7 Correct 85 ms 10488 KB ok, correct split
8 Correct 133 ms 13048 KB ok, correct split
9 Correct 80 ms 10624 KB ok, correct split
10 Correct 66 ms 11376 KB ok, correct split
11 Correct 63 ms 11376 KB ok, correct split
12 Correct 65 ms 11376 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Incorrect 84 ms 11140 KB invalid split: #1=20000, #2=21840, #3=58160
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 954 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 6 ms 4988 KB ok, correct split
2 Correct 7 ms 4984 KB ok, correct split
3 Correct 6 ms 4988 KB ok, correct split
4 Correct 6 ms 4984 KB ok, correct split
5 Correct 6 ms 4984 KB ok, correct split
6 Correct 7 ms 4984 KB ok, correct split
7 Correct 102 ms 10616 KB ok, correct split
8 Correct 84 ms 10488 KB ok, correct split
9 Correct 86 ms 10616 KB ok, correct split
10 Correct 100 ms 11640 KB ok, correct split
11 Correct 94 ms 11640 KB ok, correct split
12 Correct 6 ms 4988 KB ok, correct split
13 Correct 11 ms 4984 KB ok, correct split
14 Correct 6 ms 4984 KB ok, correct split
15 Correct 113 ms 11612 KB ok, correct split
16 Correct 74 ms 10628 KB ok, correct split
17 Correct 86 ms 10496 KB ok, correct split
18 Correct 85 ms 10488 KB ok, correct split
19 Correct 133 ms 13048 KB ok, correct split
20 Correct 80 ms 10624 KB ok, correct split
21 Correct 66 ms 11376 KB ok, correct split
22 Correct 63 ms 11376 KB ok, correct split
23 Correct 65 ms 11376 KB ok, correct split
24 Correct 6 ms 4984 KB ok, correct split
25 Incorrect 84 ms 11140 KB invalid split: #1=20000, #2=21840, #3=58160
26 Halted 0 ms 0 KB -