oj.uz

Submission #161750

# Submission time Handle Problem Language Result Execution time Memory
161750 2019-11-04T11:00:50 Z andrew Split the Attractions (IOI19_split) C++17
0 / 100
 212 ms 33144 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(!c)break;
                c--;
                res[x] = 3;
            }
            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] = 2;
        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
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 27 ms 26744 KB ok, correct split
4 Correct 28 ms 26744 KB ok, correct split
5 Correct 28 ms 26744 KB ok, correct split
6 Correct 27 ms 26744 KB ok, correct split
7 Correct 212 ms 31992 KB ok, correct split
8 Incorrect 97 ms 31736 KB 2 components are not connected
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26744 KB ok, correct split
2 Correct 27 ms 26708 KB ok, correct split
3 Correct 32 ms 26716 KB ok, correct split
4 Correct 126 ms 33144 KB ok, correct split
5 Incorrect 100 ms 31992 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 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 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 27 ms 26744 KB ok, correct split
2 Correct 27 ms 26744 KB ok, correct split
3 Correct 27 ms 26744 KB ok, correct split
4 Correct 28 ms 26744 KB ok, correct split
5 Correct 28 ms 26744 KB ok, correct split
6 Correct 27 ms 26744 KB ok, correct split
7 Correct 212 ms 31992 KB ok, correct split
8 Incorrect 97 ms 31736 KB 2 components are not connected
9 Halted 0 ms 0 KB -