oj.uz

Submission #161749

# Submission time Handle Problem Language Result Execution time Memory
161749 2019-11-04T11:00:01 Z andrew Split the Attractions (IOI19_split) C++17
7 / 100
 138 ms 33000 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];

int start;

bool f[N];

void dfs(int x, int pr){
    if(f[x] == 1){
        start = x;
        return;
    }
    if(f[x] == 2)return;
    f[x] = 1;
    for(auto to : v[x])if(to != pr)dfs(to, x);
    f[x] = 2;
}

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;
        start = 0;
//        for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i;
//        if(v[start].size() != 1){
//            dfs(1, 0);
//        }
        q.push(start);
        vector <bool> f(n);
        f[start] = 1;
        res[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(int i = 0; i < n; i++)if(res[i] == 0)res[i] = 3;
        return res;
    }else 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{
        return res;
    }
	return res;
}

Compilation message

split.cpp: In function 'void dfs(int, int)':
split.cpp:27:13: warning: comparison of constant '2' with boolean expression is always false [-Wbool-compare]
     if(f[x] == 2)return;
        ~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26620 KB ok, correct split
2 Correct 27 ms 26744 KB ok, correct split
3 Correct 28 ms 26744 KB ok, correct split
4 Correct 29 ms 26744 KB ok, correct split
5 Correct 28 ms 26744 KB ok, correct split
6 Correct 27 ms 26720 KB ok, correct split
7 Correct 113 ms 31776 KB ok, correct split
8 Correct 115 ms 31936 KB ok, correct split
9 Correct 112 ms 31736 KB ok, correct split
10 Correct 100 ms 31844 KB ok, correct split
11 Correct 115 ms 31836 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 41 ms 26744 KB ok, correct split
3 Correct 30 ms 26744 KB ok, correct split
4 Correct 138 ms 33000 KB ok, correct split
5 Incorrect 122 ms 31964 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 27 ms 26744 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 29 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 28 ms 26620 KB ok, correct split
2 Correct 27 ms 26744 KB ok, correct split
3 Correct 28 ms 26744 KB ok, correct split
4 Correct 29 ms 26744 KB ok, correct split
5 Correct 28 ms 26744 KB ok, correct split
6 Correct 27 ms 26720 KB ok, correct split
7 Correct 113 ms 31776 KB ok, correct split
8 Correct 115 ms 31936 KB ok, correct split
9 Correct 112 ms 31736 KB ok, correct split
10 Correct 100 ms 31844 KB ok, correct split
11 Correct 115 ms 31836 KB ok, correct split
12 Correct 27 ms 26744 KB ok, correct split
13 Correct 41 ms 26744 KB ok, correct split
14 Correct 30 ms 26744 KB ok, correct split
15 Correct 138 ms 33000 KB ok, correct split
16 Incorrect 122 ms 31964 KB 2 components are not connected
17 Halted 0 ms 0 KB -