oj.uz

Submission #465034

# Submission time Handle Problem Language Result Execution time Memory
465034 2021-08-14T21:50:46 Z solver1104 Regions (IOI09_regions) C++11
30 / 100
 2657 ms 131076 KB 
//#pragma warning( disable : 4996 )
#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 5;
const int MAX2 = 25000;
int N, R, Q, tmp, tmp1;
int startingtimes[MAX], endingtimes[MAX], home[MAX];
vector<int> adj[MAX];
map<int, int> homeregions[MAX];
map<int, int> monitored[MAX2];

void dfs(int node = 0, int parent = -1) {
    for (int i : adj[node]) {
        if (i != parent) {
            dfs(i, node);
            if (homeregions[i].size() > homeregions[node].size()) {
                swap(homeregions[i], homeregions[node]);
            }

            for (auto x : homeregions[i]) {
                homeregions[node][x.first] += x.second;
            }
            homeregions[i].clear();
        }
    }
    for (auto i : homeregions[node]) {
        monitored[home[node]][i.first] += i.second;
    }
}

int main()
{
    /*
    string problemName = "";
    ifstream fin(problemName + ".in");
    ofstream fout(problemName + ".out");
    */

    cin >> N >> R >> Q;
    cin >> tmp;
    homeregions[0][tmp] ++;
    home[0] = tmp;

    for (int i = 1; i < N; i++) {
        cin >> tmp >> tmp1;
        adj[i].push_back(tmp - 1);
        adj[tmp - 1].push_back(i);
        homeregions[i][tmp1] ++;
        home[i] = tmp1;
    }
    dfs();

    for (int i = 0; i < Q; i++) {
        cin >> tmp >> tmp1;
        cout << monitored[tmp][tmp1] << "\n";
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15564 KB Output is correct
2 Correct 10 ms 15560 KB Output is correct
3 Correct 11 ms 15560 KB Output is correct
4 Correct 15 ms 15600 KB Output is correct
5 Correct 13 ms 15688 KB Output is correct
6 Correct 42 ms 18132 KB Output is correct
7 Correct 43 ms 16328 KB Output is correct
8 Correct 63 ms 17216 KB Output is correct
9 Correct 183 ms 20824 KB Output is correct
10 Correct 153 ms 21960 KB Output is correct
11 Correct 239 ms 19908 KB Output is correct
12 Correct 588 ms 27148 KB Output is correct
13 Correct 195 ms 20076 KB Output is correct
14 Correct 201 ms 19444 KB Output is correct
15 Correct 906 ms 27716 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1418 ms 25740 KB Output is correct
2 Correct 1062 ms 23836 KB Output is correct
3 Correct 2657 ms 31392 KB Output is correct
4 Runtime error 770 ms 131076 KB Execution killed with signal 9
5 Runtime error 1068 ms 131076 KB Execution killed with signal 9
6 Runtime error 779 ms 131076 KB Execution killed with signal 9
7 Runtime error 576 ms 131076 KB Execution killed with signal 9
8 Runtime error 917 ms 131076 KB Execution killed with signal 9
9 Runtime error 642 ms 131076 KB Execution killed with signal 9
10 Runtime error 934 ms 131076 KB Execution killed with signal 9
11 Runtime error 771 ms 131076 KB Execution killed with signal 9
12 Runtime error 958 ms 131076 KB Execution killed with signal 9
13 Runtime error 840 ms 131076 KB Execution killed with signal 9
14 Runtime error 805 ms 131076 KB Execution killed with signal 9
15 Runtime error 690 ms 131076 KB Execution killed with signal 9
16 Runtime error 591 ms 131076 KB Execution killed with signal 9
17 Runtime error 727 ms 131076 KB Execution killed with signal 9