oj.uz

답안 #161788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161788 2019-11-04T12:14:26 Z andrew Split the Attractions (IOI19_split) C++17
11 / 100
 944 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){
    //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, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 7 ms 4984 KB ok, correct split
3 Correct 7 ms 4984 KB ok, correct split
4 Runtime error 944 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 6 ms 4956 KB ok, correct split
3 Correct 6 ms 4984 KB ok, correct split
4 Correct 98 ms 11636 KB ok, correct split
5 Correct 78 ms 10720 KB ok, correct split
6 Correct 77 ms 10492 KB ok, correct split
7 Correct 76 ms 10488 KB ok, correct split
8 Correct 125 ms 13040 KB ok, correct split
9 Correct 78 ms 10488 KB ok, correct split
10 Correct 63 ms 11376 KB ok, correct split
11 Correct 65 ms 11248 KB ok, correct split
12 Correct 68 ms 11248 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Incorrect 86 ms 11104 KB invalid split: #1=20000, #2=21840, #3=58160
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 914 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB ok, correct split
2 Correct 7 ms 4984 KB ok, correct split
3 Correct 7 ms 4984 KB ok, correct split
4 Runtime error 944 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -