oj.uz

Submission #161752

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

vector <ll> d;

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;
}
int C;
void go(int x){
    if(f[x])return;
    if(!C)return;
    C--;
    d.push_back(x);
    f[x] = 1;
    for(auto to : v[x])go(to);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = p.size(), mx = 0;
    C = c;
    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);
        f[start] = 1;
        res[start] = 1;

        for(auto to : v[start])go(to);
        for(auto i : d)res[i] = 3;
        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:29: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 27 ms 26744 KB ok, correct split
2 Correct 28 ms 26872 KB ok, correct split
3 Correct 26 ms 26744 KB ok, correct split
4 Correct 26 ms 26744 KB ok, correct split
5 Correct 27 ms 26744 KB ok, correct split
6 Correct 26 ms 26744 KB ok, correct split
7 Correct 100 ms 31868 KB ok, correct split
8 Correct 101 ms 31864 KB ok, correct split
9 Correct 107 ms 31860 KB ok, correct split
10 Correct 124 ms 37560 KB ok, correct split
11 Correct 109 ms 31880 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26740 KB ok, correct split
2 Correct 27 ms 26744 KB ok, correct split
3 Correct 28 ms 26692 KB ok, correct split
4 Correct 138 ms 36428 KB ok, correct split
5 Incorrect 100 ms 32636 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 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 28 ms 26872 KB ok, correct split
3 Correct 26 ms 26744 KB ok, correct split
4 Correct 26 ms 26744 KB ok, correct split
5 Correct 27 ms 26744 KB ok, correct split
6 Correct 26 ms 26744 KB ok, correct split
7 Correct 100 ms 31868 KB ok, correct split
8 Correct 101 ms 31864 KB ok, correct split
9 Correct 107 ms 31860 KB ok, correct split
10 Correct 124 ms 37560 KB ok, correct split
11 Correct 109 ms 31880 KB ok, correct split
12 Correct 28 ms 26740 KB ok, correct split
13 Correct 27 ms 26744 KB ok, correct split
14 Correct 28 ms 26692 KB ok, correct split
15 Correct 138 ms 36428 KB ok, correct split
16 Incorrect 100 ms 32636 KB 2 components are not connected
17 Halted 0 ms 0 KB -