oj.uz

Submission #161789

# Submission time Handle Problem Language Result Execution time Memory
161789 2019-11-04T12:16:06 Z andrew Split the Attractions (IOI19_split) C++17
11 / 100
 129 ms 17272 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){
    if(t[x])return;
    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(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
0 / 7.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 4984 KB ok, correct split
4 Correct 7 ms 4984 KB ok, correct split
5 Correct 7 ms 4984 KB ok, correct split
6 Correct 7 ms 4984 KB ok, correct split
7 Correct 109 ms 17224 KB ok, correct split
8 Correct 80 ms 10456 KB ok, correct split
9 Incorrect 121 ms 17272 KB invalid split: #1=57251, #2=42747, #3=2
10 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB ok, correct split
2 Correct 7 ms 4984 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 106 ms 11612 KB ok, correct split
5 Correct 78 ms 10744 KB ok, correct split
6 Correct 74 ms 10492 KB ok, correct split
7 Correct 76 ms 10616 KB ok, correct split
8 Correct 129 ms 13188 KB ok, correct split
9 Correct 96 ms 10488 KB ok, correct split
10 Correct 65 ms 11392 KB ok, correct split
11 Correct 68 ms 11376 KB ok, correct split
12 Correct 69 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 91 ms 11128 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 Correct 6 ms 4988 KB ok, correct split
2 Correct 6 ms 4984 KB ok, no valid answer
3 Correct 6 ms 4984 KB ok, correct split
4 Incorrect 7 ms 4984 KB invalid split: #1=2, #2=3, #3=6
5 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 4984 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 7 ms 4984 KB ok, correct split
5 Correct 7 ms 4984 KB ok, correct split
6 Correct 7 ms 4984 KB ok, correct split
7 Correct 109 ms 17224 KB ok, correct split
8 Correct 80 ms 10456 KB ok, correct split
9 Incorrect 121 ms 17272 KB invalid split: #1=57251, #2=42747, #3=2
10 Halted 0 ms 0 KB -