oj.uz

Submission #161734

# Submission time Handle Problem Language Result Execution time Memory
161734 2019-11-04T09:57:01 Z andrew Split the Attractions (IOI19_split) C++17
7 / 100
 119 ms 31880 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();
            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 27 ms 26744 KB ok, correct split
3 Correct 28 ms 26616 KB ok, correct split
4 Correct 27 ms 26744 KB ok, correct split
5 Correct 27 ms 26744 KB ok, correct split
6 Correct 27 ms 26616 KB ok, correct split
7 Correct 119 ms 31880 KB ok, correct split
8 Correct 98 ms 31864 KB ok, correct split
9 Correct 100 ms 31864 KB ok, correct split
10 Correct 95 ms 31864 KB ok, correct split
11 Correct 99 ms 31864 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 26744 KB ok, correct split
2 Correct 28 ms 26744 KB ok, correct split
3 Incorrect 27 ms 26700 KB invalid split: #1=0, #2=1, #3=4
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 26616 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 27 ms 26744 KB ok, correct split
3 Correct 28 ms 26616 KB ok, correct split
4 Correct 27 ms 26744 KB ok, correct split
5 Correct 27 ms 26744 KB ok, correct split
6 Correct 27 ms 26616 KB ok, correct split
7 Correct 119 ms 31880 KB ok, correct split
8 Correct 98 ms 31864 KB ok, correct split
9 Correct 100 ms 31864 KB ok, correct split
10 Correct 95 ms 31864 KB ok, correct split
11 Correct 99 ms 31864 KB ok, correct split
12 Correct 27 ms 26744 KB ok, correct split
13 Correct 28 ms 26744 KB ok, correct split
14 Incorrect 27 ms 26700 KB invalid split: #1=0, #2=1, #3=4
15 Halted 0 ms 0 KB -