Submission #541532

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
541532	2022-03-23T18:03:17 Z	Olympia	Uzastopni (COCI15_uzastopni)	C++17	80 / 160	124 ms	13132 KB

uzastopni

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <limits.h>

using namespace std;
vector<vector<pair<pair<int, int>, int>>> sub;
vector<vector<int>> adj;
vector<int> v;

void dfs(int curNode, int prevNode) {
    vector<int> children;
    vector<pair<pair<int, int>, int>> left, right;
    for (int i: adj[curNode]) {
        if (i == prevNode) {
            continue;
        }
        dfs(i, curNode);
        for (auto &p: sub[i]) {
            if (p.first.first <= v[curNode] && v[curNode] <= p.first.second) {
                continue;
            }
            if (p.first.first < v[curNode]) left.emplace_back(p);
            else right.emplace_back(p);
        }
    }
    map<int, int> dpL, dpR;
    dpL[v[curNode]] = dpR[v[curNode]] = 1;
    sort(left.begin(), left.end()); reverse(left.begin(), left.end());
    for (auto &p: left) {
        dpL[p.first.first] += dpL[p.first.second + 1] * p.second;
    }
    sort(right.begin(), right.end());
    for (auto &p: right) {
        dpR[p.first.second] += dpR[p.first.first - 1] * p.second;
    }
    map<pair<int, int>, int> myMap;
    for (auto &l: dpL) {
        for (auto &r: dpR) {
            myMap[{l.first, r.first}] += l.second * r.second;
        }
    }
    for (auto &p: myMap) {
        if (p.second != 0) {
            sub[curNode].push_back(p);
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    adj.resize(N);
    v.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> v[i];
        v[i]--;
    }
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back(y), adj[y].push_back(x);
    }
    sub.resize(N);
    dfs(0, -1);
    int ans = 0;
    for (auto &p: sub[0]) {
        //cout << p.first.first << " " << p.first.second << " " << p.second << '\n';
        ans += p.second;
    }
    cout << ans << '\n';

}

Subtask #1

80.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Incorrect	0 ms	212 KB	Output isn't correct
5	Incorrect	1 ms	212 KB	Output isn't correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Incorrect	9 ms	1492 KB	Output isn't correct
12	Incorrect	9 ms	1500 KB	Output isn't correct
13	Incorrect	8 ms	1492 KB	Output isn't correct
14	Incorrect	111 ms	13084 KB	Output isn't correct
15	Correct	124 ms	13132 KB	Output is correct
16	Incorrect	107 ms	13132 KB	Output isn't correct
17	Incorrect	8 ms	1492 KB	Output isn't correct
18	Incorrect	8 ms	1492 KB	Output isn't correct
19	Correct	37 ms	5000 KB	Output is correct
20	Correct	38 ms	5196 KB	Output is correct