Submission #1039042

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039042	2024-07-30T11:12:15 Z	Zicrus	Beech Tree (IOI23_beechtree)	C++17	9 / 100	86 ms	20960 KB

beechtree

#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;

typedef long long ll;

vector<int> beechtree(int n, int m, vector<int> p, vector<int> c) {
    vector<int> res(n, 1);
    vector<vector<ll>> adj(n);
    for (int i = 1; i < n; i++) {
        adj[p[i]].push_back(i);
    }
    vector<pair<ll, ll>> szId(n);
    for (int i = 0; i < n; i++) {
        szId[i] = {adj[i].size(), i};
    }
    sort(szId.begin(), szId.end());
    unordered_set<ll> used;
    if (adj[0].size() != szId.back().first) res[0] = 0;
    for (auto &e : adj[0]) {
        if (used.count(c[e]))
            res[0] = 0;
        used.insert(c[e]);
    }
    for (int i = n-1; i >= 1; i--) {
        unordered_set<ll> nw;
        for (auto &e : adj[szId[i].second]) {
            if (!used.count(c[e]))
                res[0] = 0;
            if (nw.count(c[e]))
                res[szId[i].second] = res[0] = 0;
            nw.insert(c[e]);
        }
        used = nw;
    }
    return res;
}

Compilation message

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:19:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   19 |     if (adj[0].size() != szId.back().first) res[0] = 0;
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 5.0

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

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 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	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 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	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	41 ms	8536 KB	Output is correct
16	Correct	42 ms	8488 KB	Output is correct
17	Correct	38 ms	8284 KB	Output is correct
18	Correct	40 ms	8540 KB	Output is correct

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	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Incorrect	86 ms	20960 KB	2nd lines differ - on the 2nd token, expected: '0', found: '1'
6	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

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