oj.uz

Submission #161736

# Submission time Handle Problem Language Result Execution time Memory
161736 2019-11-04T10:04:38 Z andrew Split the Attractions (IOI19_split) C++17
7 / 100
 153 ms 36472 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;
        int start = 0;
        for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i;
        res[start] = 1;
        q.push(start);
        vector <bool> f(n);
        f[start] = 1;

        while(!q.empty()){
            int x = q.front();
            q.pop();
            if(x != start){
                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 29 ms 26616 KB ok, correct split
2 Correct 27 ms 26748 KB ok, correct split
3 Correct 27 ms 26744 KB ok, correct split
4 Correct 27 ms 26744 KB ok, correct split
5 Correct 28 ms 26744 KB ok, correct split
6 Correct 27 ms 26716 KB ok, correct split
7 Correct 107 ms 31864 KB ok, correct split
8 Correct 104 ms 31864 KB ok, correct split
9 Correct 102 ms 31736 KB ok, correct split
10 Correct 109 ms 31736 KB ok, correct split
11 Correct 109 ms 31736 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 26616 KB ok, correct split
2 Correct 27 ms 26616 KB ok, correct split
3 Correct 27 ms 26616 KB ok, correct split
4 Correct 122 ms 32888 KB ok, correct split
5 Correct 108 ms 31992 KB ok, correct split
6 Correct 116 ms 32888 KB ok, correct split
7 Correct 112 ms 32892 KB ok, correct split
8 Correct 153 ms 36472 KB ok, correct split
9 Incorrect 118 ms 33016 KB 2 components are not connected
10 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 26716 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 26616 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 29 ms 26616 KB ok, correct split
2 Correct 27 ms 26748 KB ok, correct split
3 Correct 27 ms 26744 KB ok, correct split
4 Correct 27 ms 26744 KB ok, correct split
5 Correct 28 ms 26744 KB ok, correct split
6 Correct 27 ms 26716 KB ok, correct split
7 Correct 107 ms 31864 KB ok, correct split
8 Correct 104 ms 31864 KB ok, correct split
9 Correct 102 ms 31736 KB ok, correct split
10 Correct 109 ms 31736 KB ok, correct split
11 Correct 109 ms 31736 KB ok, correct split
12 Correct 41 ms 26616 KB ok, correct split
13 Correct 27 ms 26616 KB ok, correct split
14 Correct 27 ms 26616 KB ok, correct split
15 Correct 122 ms 32888 KB ok, correct split
16 Correct 108 ms 31992 KB ok, correct split
17 Correct 116 ms 32888 KB ok, correct split
18 Correct 112 ms 32892 KB ok, correct split
19 Correct 153 ms 36472 KB ok, correct split
20 Incorrect 118 ms 33016 KB 2 components are not connected
21 Halted 0 ms 0 KB -