oj.uz

Submission #161774

# Submission time Handle Problem Language Result Execution time Memory
161774 2019-11-04T11:43:25 Z andrew Split the Attractions (IOI19_split) C++17
11 / 100
 965 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[MAXN];

ll t[MAXN], P[MAXN];

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

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 <ll> cnt(3);
        vector <bool> f(n);
        cnt[0] = a;
        cnt[1] = b;
        cnt[2] = c;
        vector <ll> 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 28 ms 26744 KB ok, correct split
2 Correct 28 ms 26744 KB ok, correct split
3 Correct 28 ms 26744 KB ok, correct split
4 Runtime error 938 ms 1048576 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 28 ms 26744 KB ok, correct split
2 Correct 60 ms 26744 KB ok, correct split
3 Correct 28 ms 26744 KB ok, correct split
4 Correct 116 ms 32924 KB ok, correct split
5 Correct 102 ms 31996 KB ok, correct split
6 Correct 98 ms 31864 KB ok, correct split
7 Correct 105 ms 31792 KB ok, correct split
8 Correct 140 ms 34316 KB ok, correct split
9 Correct 102 ms 31864 KB ok, correct split
10 Correct 87 ms 32624 KB ok, correct split
11 Correct 88 ms 32624 KB ok, correct split
12 Correct 93 ms 32752 KB ok, correct split

Subtask #3
0 / 22.0

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

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 965 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 28 ms 26744 KB ok, correct split
2 Correct 28 ms 26744 KB ok, correct split
3 Correct 28 ms 26744 KB ok, correct split
4 Runtime error 938 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -