oj.uz

Submission #161735

# Submission time Handle Problem Language Result Execution time Memory
161735 2019-11-04T10:00:53 Z andrew Split the Attractions (IOI19_split) C++17
7 / 100
 121 ms 34556 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];

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(mx < 3){
        int F = 0, Last = 0;
        for(int i = 0; i < n; i++)if(v[i].size() == 1)F = i;
        int step = 1;
        vector <int> cnt(3);
        cnt[0] = a;
        cnt[1] = b;
        cnt[2] = c;
        for(int i = 0; i < n; i++){
            if(i){
                int New = 0;
                for(auto j : v[F])if(j != Last)New = j;
                Last = F;
                F = New;
            }
            while(!cnt[step - 1])step++;
            --cnt[step - 1];
            res[F] = step;
        }
        return res;
    }else if(a == 1){
        queue <int> q;
        res[0] = 1;
        q.push(0);
        vector <bool> f(n);
        f[0] = 1;

        while(!q.empty()){
            int x = q.front();
            q.pop();
            if(x){
                if(!b)break;
                b--;
                res[x] = 2;
            }

            for(auto to : v[x])if(!f[to]){
                f[to] = 1;
                q.push(to);
            }
        }

        for(auto &i : res)if(!i)i = 3;

        return res;
    }else{
        return res;
    }
	return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 26744 KB ok, correct split
2 Correct 29 ms 26616 KB ok, correct split
3 Correct 27 ms 26616 KB ok, correct split
4 Correct 27 ms 26744 KB ok, correct split
5 Correct 27 ms 26616 KB ok, correct split
6 Correct 28 ms 26616 KB ok, correct split
7 Correct 110 ms 31864 KB ok, correct split
8 Correct 115 ms 31864 KB ok, correct split
9 Correct 106 ms 31864 KB ok, correct split
10 Correct 100 ms 31864 KB ok, correct split
11 Correct 100 ms 31788 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 26616 KB ok, correct split
2 Correct 27 ms 26616 KB ok, correct split
3 Correct 27 ms 26696 KB ok, correct split
4 Correct 121 ms 34556 KB ok, correct split
5 Incorrect 104 ms 33144 KB 2 components are not connected
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 26748 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 26744 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 26744 KB ok, correct split
2 Correct 29 ms 26616 KB ok, correct split
3 Correct 27 ms 26616 KB ok, correct split
4 Correct 27 ms 26744 KB ok, correct split
5 Correct 27 ms 26616 KB ok, correct split
6 Correct 28 ms 26616 KB ok, correct split
7 Correct 110 ms 31864 KB ok, correct split
8 Correct 115 ms 31864 KB ok, correct split
9 Correct 106 ms 31864 KB ok, correct split
10 Correct 100 ms 31864 KB ok, correct split
11 Correct 100 ms 31788 KB ok, correct split
12 Correct 27 ms 26616 KB ok, correct split
13 Correct 27 ms 26616 KB ok, correct split
14 Correct 27 ms 26696 KB ok, correct split
15 Correct 121 ms 34556 KB ok, correct split
16 Incorrect 104 ms 33144 KB 2 components are not connected
17 Halted 0 ms 0 KB -