oj.uz

Submission #161779

# Submission time Handle Problem Language Result Execution time Memory
161779 2019-11-04T12:00:39 Z andrew Split the Attractions (IOI19_split) C++17
11 / 100
 952 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){
        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 <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, 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 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 949 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 28 ms 26744 KB ok, correct split
2 Correct 29 ms 26688 KB ok, correct split
3 Correct 30 ms 26744 KB ok, correct split
4 Correct 122 ms 33400 KB ok, correct split
5 Correct 107 ms 32504 KB ok, correct split
6 Correct 97 ms 32348 KB ok, correct split
7 Correct 103 ms 32348 KB ok, correct split
8 Correct 142 ms 34808 KB ok, correct split
9 Correct 101 ms 32376 KB ok, correct split
10 Correct 89 ms 33396 KB ok, correct split
11 Correct 90 ms 33392 KB ok, correct split
12 Correct 95 ms 33268 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26744 KB ok, correct split
2 Incorrect 112 ms 34040 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 952 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 949 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -