oj.uz

Submission #841438

# Submission time Handle Problem Language Result Execution time Memory
841438 2023-09-01T15:40:11 Z model_code Beech Tree (IOI23_beechtree) C++17
5 / 100
 353 ms 101996 KB 
// incorrect/solution-amshz-wa.cpp

#include "beechtree.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

#define F first
#define S second

const int xn = 2e5 + 10;

int n, m, par[xn], a[xn], sz[xn];
pii dsu[xn];
vector<int> adj[xn];
set<pii> st[xn], chil[xn];
bool ans[xn], ns[xn];
map<int, int> mp[xn];

bool is_ok(int v, int u)
{
    for (int x : adj[v])
        if (mp[u][a[x]] < sz[x])
            return false;
    return true;
}
int get_root(int v)
{
    if (v == dsu[v].F)
        return v;
    return dsu[v].F = get_root(dsu[v].F);
}
void merge(int v, int u)
{
    v = get_root(v);
    u = get_root(u);
    if (dsu[v].S < dsu[u].S)
        swap(v, u);
    dsu[u].F = v;
    dsu[v].S += dsu[u].S;
    if (!ns[v] || !ns[u])
    {
        ns[v] = false;
        return;
    }
    for (pii x : st[u])
    {
        st[v].insert(x);
        auto it = st[v].find(x);
        it++;
        if (it != st[v].end())
        {
            int next_ver = it->S;
            if (!is_ok(x.S, next_ver))
            {
                ns[v] = false;
                break;
            }
        }
        it--;
        if (it != st[v].begin())
        {
            it--;
            int prev_ver = it->S;
            if (!is_ok(prev_ver, x.S))
            {
                ns[v] = false;
                break;
            }
        }
        st[v].insert(x);
    }
}
void DFS(int v)
{
    sz[v] = 1;
    for (int u : adj[v])
    {
        DFS(u);
        sz[v] += sz[u];
        mp[v][a[u]] = sz[u];
    }
    st[v].insert({sz[v], v});
    dsu[v] = {v, 1};
    ns[v] = true;
    for (int u : adj[v])
        merge(v, u);
    ans[v] = ns[get_root(v)];
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
    n = N - 1, m = M;
    for (int i = 1; i <= n; ++i)
    {
        par[i] = P[i], a[i] = C[i];
        adj[par[i]].push_back(i);
    }
    DFS(0);
    vector<int> ret(N);
    for (int i = 0; i <= n; ++i)
        ret[i] = ans[i];
    return ret;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 33124 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33208 KB Output is correct
2 Correct 20 ms 33192 KB Output is correct
3 Correct 31 ms 33144 KB Output is correct
4 Correct 17 ms 33120 KB Output is correct
5 Correct 22 ms 34192 KB Output is correct
6 Correct 21 ms 33120 KB Output is correct
7 Incorrect 19 ms 34320 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
8 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33208 KB Output is correct
2 Correct 20 ms 33192 KB Output is correct
3 Correct 31 ms 33144 KB Output is correct
4 Correct 17 ms 33120 KB Output is correct
5 Correct 22 ms 34192 KB Output is correct
6 Correct 21 ms 33120 KB Output is correct
7 Correct 196 ms 93312 KB Output is correct
8 Correct 146 ms 93920 KB Output is correct
9 Correct 22 ms 33208 KB Output is correct
10 Correct 20 ms 33364 KB Output is correct
11 Correct 19 ms 33388 KB Output is correct
12 Correct 63 ms 34044 KB Output is correct
13 Correct 25 ms 34044 KB Output is correct
14 Correct 33 ms 34364 KB Output is correct
15 Correct 19 ms 33812 KB Output is correct
16 Correct 24 ms 33708 KB Output is correct
17 Correct 281 ms 101996 KB Output is correct
18 Correct 276 ms 98088 KB Output is correct
19 Correct 200 ms 93664 KB Output is correct
20 Correct 353 ms 91816 KB Output is correct

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 33280 KB Output is correct
2 Incorrect 19 ms 33244 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33208 KB Output is correct
2 Correct 20 ms 33192 KB Output is correct
3 Incorrect 19 ms 34320 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 33124 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33208 KB Output is correct
2 Correct 20 ms 33192 KB Output is correct
3 Incorrect 19 ms 34320 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 33124 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33208 KB Output is correct
2 Correct 20 ms 33192 KB Output is correct
3 Incorrect 19 ms 34320 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 33124 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -