oj.uz

답안 #1068932

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068932 2024-08-21T13:27:41 Z parsadox2 참나무 (IOI23_beechtree) C++17
0 / 100
 2000 ms 2097152 KB 
#include "beechtree.h"
#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int N = 2e5 + 10;

int n , m , col[N];
vector <int> p , adj[N] , all_col[N] , all_deg[N];
bool bad[N] , marked[N];
vector <int> all;

void Dfs(int v)
{
    all.push_back(v);
    all_deg[v].push_back(adj[v].size());
    for(auto u : adj[v])
    {
        all_deg[u] = all_deg[v];
        Dfs(u);
    }
}

bool cmp(vector <int> aa , vector <int> bb)
{
    return aa.size() > bb.size();
}

bool Sub_seq(vector <int> aa , vector <int> bb)
{
    if(aa.size() > bb.size())
        swap(aa , bb);
    for(auto u : aa)
        marked[u] = true;
    for(auto u : bb)
        marked[u] = false;
    bool flg = true;
    for(auto u : aa)  if(marked[u])
    {
        marked[u] = false;
        flg = false;
    }
    return flg;
}

bool Check(int aa , int bb)
{
    for(int i = 1 ; i < all_deg[aa].size() ; i++)  if(all_deg[aa][i - 1] < all_deg[aa][i])
        return false;
    for(int i = 1 ; i < all_deg[bb].size() ; i++)  if(all_deg[bb][i - 1] < all_deg[bb][i])
        return false;
    bool flga = false , flgb = false;
    for(int i = 0 ; i < min(all_deg[aa].size() , all_deg[bb].size()) ; i++)
    {
        if(all_deg[aa][i] < all_deg[bb][i])
            flga = true;
        if(all_deg[bb][i] < all_deg[aa][i])
            flgb = true;
    }
    if(flga && flgb)
        return false;
    return true;
}

bool Solve(int v)
{
    all_deg[v].clear();
    all.clear();
    Dfs(v);
    for(auto u : all)  if(bad[u])
        return false;
    vector <vector<int>> vec;
    for(auto u : all)
        vec.push_back(all_col[u]);
    sort(vec.begin() , vec.end() , cmp);
    for(int i = 1 ; i < all.size() ; i++)  if(!Sub_seq(vec[i] , vec[i - 1]))
        return false;
    for(auto x : all)  for(auto y : all)  if(!Check(x , y))
        return false;
    return true;
}

vector<int> beechtree(int nn, int mm, vector<int> P, vector<int> C)
{
    n = nn;  
    m = mm;
    p = P;
    for(int i = 1 ; i < n ; i++)
    {
        adj[P[i]].push_back(i);
        col[i] = C[i];
    }
    for(int i = 0 ; i < n ; i++)
    {
        for(auto u : adj[i])
            all_col[i].push_back(col[u]);
        sort(all_col[i].begin() , all_col[i].end());
        for(int j = 1 ; j < all_col[i].size() ; j++)  if(all_col[i][j] == all_col[i][j - 1])
            bad[i] = true;
    }
    vector <int> res;
    for(int i = 0 ; i < n ; i++)
        res.push_back(Solve(i));
    return res;
}

Compilation message

beechtree.cpp: In function 'bool Check(int, int)':
beechtree.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 1 ; i < all_deg[aa].size() ; i++)  if(all_deg[aa][i - 1] < all_deg[aa][i])
      |                     ~~^~~~~~~~~~~~~~~~~~~~
beechtree.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 1 ; i < all_deg[bb].size() ; i++)  if(all_deg[bb][i - 1] < all_deg[bb][i])
      |                     ~~^~~~~~~~~~~~~~~~~~~~
beechtree.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   56 |     for(int i = 0 ; i < min(all_deg[aa].size() , all_deg[bb].size()) ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beechtree.cpp: In function 'bool Solve(int)':
beechtree.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 1 ; i < all.size() ; i++)  if(!Sub_seq(vec[i] , vec[i - 1]))
      |                     ~~^~~~~~~~~~~~
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int j = 1 ; j < all_col[i].size() ; j++)  if(all_col[i][j] == all_col[i][j - 1])
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct

Subtask #1
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 3 ms 14808 KB Output is correct
11 Correct 3 ms 14680 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14840 KB Output is correct
14 Correct 3 ms 14792 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 2 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Incorrect 2 ms 14684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
19 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Runtime error 1041 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14784 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 2 ms 14808 KB Output is correct
8 Correct 3 ms 15036 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 2 ms 14784 KB Output is correct
11 Correct 4 ms 14944 KB Output is correct
12 Correct 4 ms 14824 KB Output is correct
13 Correct 4 ms 15068 KB Output is correct
14 Correct 12 ms 14940 KB Output is correct
15 Correct 262 ms 26484 KB Output is correct
16 Correct 250 ms 26688 KB Output is correct
17 Correct 248 ms 26052 KB Output is correct
18 Execution timed out 2058 ms 27468 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Runtime error 1041 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 3 ms 14808 KB Output is correct
14 Correct 3 ms 14680 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14840 KB Output is correct
17 Correct 3 ms 14792 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 2 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Incorrect 2 ms 14684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 3 ms 14808 KB Output is correct
7 Correct 3 ms 14680 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14840 KB Output is correct
10 Correct 3 ms 14792 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Incorrect 2 ms 14684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 3 ms 14808 KB Output is correct
14 Correct 3 ms 14680 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14840 KB Output is correct
17 Correct 3 ms 14792 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 2 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Incorrect 2 ms 14684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 3 ms 14808 KB Output is correct
7 Correct 3 ms 14680 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14840 KB Output is correct
10 Correct 3 ms 14792 KB Output is correct
11 Correct 3 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Incorrect 2 ms 14684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14936 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 2 ms 14684 KB Output is correct
13 Correct 3 ms 14808 KB Output is correct
14 Correct 3 ms 14680 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14840 KB Output is correct
17 Correct 3 ms 14792 KB Output is correct
18 Correct 3 ms 14684 KB Output is correct
19 Correct 2 ms 14684 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Incorrect 2 ms 14684 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -