oj.uz

답안 #1029612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029612 2024-07-21T06:04:55 Z Mr_Husanboy 참나무 (IOI23_beechtree) C++17
5 / 100
 49 ms 18636 KB 
#include "beechtree.h"
#include <bits/stdc++.h>


#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){
    return a.size();
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

vector<int> beechtree(int n, int m, std::vector<int> par, std::vector<int> col)
{
    vector<vector<int>> g(n);
    for(int i = 1; i < n; i ++){
        g[par[i]].push_back(i);
        col[i] --;
    }

    vector<int> res(n);
    vector<int> cnt(m + 1);
    for(int i = n - 1; i >= 0; i --){
        res[i] = 1;
        if(col[i] != col.back()) break;
    }
    return res;

    auto check = [&](int &node, vector<int> &perm){
        if(perm[0] != node) return false;
        vector<int> f(len(perm));


        for(int i = 1; i < len(perm); i ++){
            f[i] = cnt[col[perm[i]]];
            cnt[col[perm[i]]] ++;
        }
        for(int i = 1; i < len(perm); i ++) cnt[col[perm[i]]] --;
        //debug(f, cnt);
        for(int i = 1; i < len(perm); i ++){
            if(perm[f[i]] != par[perm[i]]) return false;
        }
        return true;
    };  


    auto dfs = [&](auto &dfs, int i)->vector<int>{
        vector<int> perm = {i};
        for(auto u : g[i]){
            auto r = dfs(dfs, u);
            if(len(perm) < len(r)) swap(perm, r);
            for(auto u : r) perm.push_back(u);
        }
        sort(all(perm));
        //debug(perm);
        do{
            if(check(i, perm)){
                res[i] = 1;
                break;
            }
        }while(next_permutation(all(perm)));

        return perm;
    };
    dfs(dfs, 0);
    return res;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
8 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 48 ms 15980 KB Output is correct
8 Correct 47 ms 18636 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 1220 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 46 ms 18128 KB Output is correct
18 Correct 46 ms 18512 KB Output is correct
19 Correct 48 ms 18516 KB Output is correct
20 Correct 49 ms 18620 KB Output is correct

Subtask #3
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -