Submission #842330

#	Time	Username	Problem	Language	Result	Execution time	Memory
842330		Itamar	참나무 (IOI23_beechtree)	C++17	0 / 100	2057 ms	27096 KiB

beechtree

//#include "beechtree.h"
#include <cassert>
#include <cstdio>
#include <cassert>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
using namespace std;
#pragma warning(disable : 4996)
#define vi vector<int>
const int siz = 2001;
const int siz2 = 2001;
vi son[siz];
int pad[siz];
int sub[siz];
int subc[siz][siz2];
bool g[siz][siz2];
int nonsubc[siz][siz2];
int h[siz];
int num[siz];
#include <algorithm>
void dfs1(int i) {
    sub[i] = 1;
    for (int f : son[i]) {
        dfs1(f);
        sub[i] += sub[f];
        
    }
}
bool fun(int i, int j) {
    return sub[j] < sub[i];
}
#include <queue>
int col[siz];
int n;
void dfs2(int i, int c) {
    int f = 0;
    for (int s : son[i]) {
        dfs2(s, c);
        if (col[s] == c)f++;
        subc[i][c] = max(subc[i][c], subc[s][c]);
        nonsubc[i][c] = min(nonsubc[i][c], nonsubc[s][c]);
        g[i][c] &= g[s][c];
    }
    if (f > 1)g[i][c] = 0;
    if (f == 1)subc[i][c] = max(subc[i][c], num[i]);
    else nonsubc[i][c] = min(nonsubc[i][c], num[i]);
    if ((subc[i][c] >= 0) && (nonsubc[i][c] <= n) && (subc[i][c] >= nonsubc[i][c]))g[i][c] = 0;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n = N;
    pad[0] = 0;
    for (int i = 1; i < N; i++) {
        pad[i] = P[i];
        son[P[i]].push_back(i);
    }
    for (int i = 0; i < N; i++)col[i] = C[i];
    dfs1(0);
    for (int i = 0; i < N; i++) {
        sort(son[i].begin(), son[i].end(), fun);
    }
    queue<int> q;
    q.push(0);
    int t = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        num[v] = t;
        t++;
        for (int f : son[v]) {
            q.push(f);
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= M; j++) {
            subc[i][j] = -1;
            nonsubc[i][j] = N + 1;
            g[i][j] = 1;
        }
    }
    for (int i = 1; i <= M; i++) {
        dfs2(0, i);
    }
    vector<int> ans(N,1);
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= M; j++) {
            ans[i] = ((ans[i])&(g[i][j]));
        }
    }
    return ans;
}

Compilation message (stderr)

beechtree.cpp:12: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
   12 | #pragma warning(disable : 4996)
      |

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12