oj.uz

Submission #999732

# Submission time Handle Problem Language Result Execution time Memory
999732 2024-06-16T06:01:57 Z 김은성(#10860) Beech Tree (IOI23_beechtree) C++17
0 / 100
 33 ms 8532 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> graph[2009];
int c[2009];
bool ans[2009], non_unique[2009];
int p[2009];
bitset<2000> color[2009], temp2;
vector<int> dfs(int v){
    int i, j, k, l;
    ans[v] = 1;
    vector<int> vec;
    vector<vector<int> > child;
    int sz = graph[v].size();
    for(i=0; i<sz; i++){
        vector<int> temp = dfs(graph[v][i]);
        child.push_back(temp);
        ans[v] &= ans[graph[v][i]];
        if((color[graph[v][i]] & color[v]) != color[graph[v][i]])
            ans[v] = 0;
        for(j=0; j<temp.size(); j++)
            vec.push_back(temp[j]);
    }
    //printf("v=%d non=%d\n", v, non_)
    if(non_unique[v])
        ans[v] = 0;
    for(i=0; i<sz; i++){
        for(j=i+1; j<sz; j++){
            for(k=0; k<child[i].size(); k++){
                for(l=0; l<child[j].size(); l++){
                    int u = child[i][k], v = child[j][v];
                    temp2 = color[u] & color[v];
                    if(temp2 == color[u] || temp2 == color[v])
                        continue;
                    ans[v] = 0;
                }
            }
        }
    }
    return vec;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C){
    int i;
    vector<int> c;
    for(i=1; i<N; i++){
        graph[P[i]].push_back(i);
        c.push_back(C[i]);
        p[i] = P[i];
    }
    sort(c.begin(), c.end());
    unique(c.begin(), c.end());
    for(i=1; i<N; i++){
        int val = lower_bound(c.begin(), c.end(), C[i]) - c.begin();
        if(color[P[i]].test(val))
            non_unique[P[i]] = 1;
        else
            color[P[i]].set(val);
    }
    dfs(0);
    vector<int> ret;
    for(i=0; i<N; i++)
        ret.push_back(ans[i]);
    return ret;
}

Compilation message

beechtree.cpp: In function 'std::vector<int> dfs(int)':
beechtree.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(j=0; j<temp.size(); j++)
      |                  ~^~~~~~~~~~~~
beechtree.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             for(k=0; k<child[i].size(); k++){
      |                      ~^~~~~~~~~~~~~~~~
beechtree.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 for(l=0; l<child[j].size(); l++){
      |                          ~^~~~~~~~~~~~~~~~
beechtree.cpp:31:56: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |                     int u = child[i][k], v = child[j][v];
      |                                                        ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 500 KB Output is correct
9 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Runtime error 33 ms 8532 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 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 #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 500 KB Output is correct
5 Runtime error 33 ms 8532 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 500 KB Output is correct
5 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 500 KB Output is correct
5 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -