oj.uz

답안 #161773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161773 2019-11-04T11:41:33 Z andrew Split the Attractions (IOI19_split) C++17
11 / 100
 1061 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, 0ll);

        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 30 ms 26744 KB ok, correct split
2 Correct 28 ms 26744 KB ok, correct split
3 Correct 29 ms 26744 KB ok, correct split
4 Runtime error 1061 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 29 ms 26744 KB ok, correct split
2 Correct 28 ms 26700 KB ok, correct split
3 Correct 27 ms 26744 KB ok, correct split
4 Correct 127 ms 32944 KB ok, correct split
5 Correct 103 ms 31992 KB ok, correct split
6 Correct 98 ms 31764 KB ok, correct split
7 Correct 99 ms 31864 KB ok, correct split
8 Correct 146 ms 34424 KB ok, correct split
9 Correct 100 ms 31864 KB ok, correct split
10 Correct 87 ms 32784 KB ok, correct split
11 Correct 86 ms 32668 KB ok, correct split
12 Correct 96 ms 32624 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 26744 KB ok, correct split
2 Incorrect 104 ms 33468 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 26744 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

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