Submission #541528

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
541528	2022-03-23T18:01:04 Z	Olympia	Uzastopni (COCI15_uzastopni)	C++17	72 / 160	83 ms	11212 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.second - 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

72.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Correct	0 ms	212 KB	Output is correct
3	Incorrect	0 ms	212 KB	Output isn't correct
4	Incorrect	1 ms	212 KB	Output isn't correct
5	Incorrect	0 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	10 ms	1468 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	82 ms	11212 KB	Output isn't correct
15	Correct	77 ms	10968 KB	Output is correct
16	Incorrect	83 ms	11152 KB	Output isn't correct
17	Incorrect	8 ms	1496 KB	Output isn't correct
18	Incorrect	12 ms	1460 KB	Output isn't correct
19	Correct	45 ms	4948 KB	Output is correct
20	Correct	39 ms	5200 KB	Output is correct