oj.uz

Submission #161784

# Submission time Handle Problem Language Result Execution time Memory
161784 2019-11-04T12:10:19 Z andrew Split the Attractions (IOI19_split) C++17
11 / 100
 926 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];

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 < 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(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);
        vector <bool> f(n);
        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, start);

        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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 Runtime error 919 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 4984 KB ok, correct split
3 Correct 6 ms 4956 KB ok, correct split
4 Correct 102 ms 11308 KB ok, correct split
5 Correct 80 ms 10232 KB ok, correct split
6 Correct 74 ms 10104 KB ok, correct split
7 Correct 81 ms 10104 KB ok, correct split
8 Correct 118 ms 12664 KB ok, correct split
9 Correct 84 ms 10104 KB ok, correct split
10 Correct 66 ms 10864 KB ok, correct split
11 Correct 67 ms 10992 KB ok, correct split
12 Correct 68 ms 10864 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 90 ms 11100 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 926 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 7 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 Runtime error 919 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -