oj.uz

Submission #464760

# Submission time Handle Problem Language Result Execution time Memory
464760 2021-08-14T00:25:35 Z solver1104 Regions (IOI09_regions) C++11
30 / 100
 3069 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;
            }
        }
    }
    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 9 ms 15560 KB Output is correct
2 Correct 9 ms 15560 KB Output is correct
3 Correct 10 ms 15576 KB Output is correct
4 Correct 12 ms 15612 KB Output is correct
5 Correct 17 ms 15688 KB Output is correct
6 Correct 36 ms 18160 KB Output is correct
7 Correct 42 ms 16456 KB Output is correct
8 Correct 49 ms 17352 KB Output is correct
9 Correct 183 ms 20800 KB Output is correct
10 Correct 149 ms 23156 KB Output is correct
11 Correct 243 ms 21148 KB Output is correct
12 Correct 593 ms 27644 KB Output is correct
13 Correct 163 ms 23496 KB Output is correct
14 Correct 234 ms 22080 KB Output is correct
15 Correct 849 ms 26548 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 26892 KB Output is correct
2 Correct 1336 ms 29052 KB Output is correct
3 Correct 3069 ms 31040 KB Output is correct
4 Runtime error 746 ms 131076 KB Execution killed with signal 9
5 Runtime error 1085 ms 131076 KB Execution killed with signal 9
6 Runtime error 757 ms 131076 KB Execution killed with signal 9
7 Runtime error 554 ms 131076 KB Execution killed with signal 9
8 Runtime error 922 ms 131076 KB Execution killed with signal 9
9 Runtime error 658 ms 131076 KB Execution killed with signal 9
10 Runtime error 960 ms 131076 KB Execution killed with signal 9
11 Runtime error 747 ms 131076 KB Execution killed with signal 9
12 Runtime error 930 ms 131076 KB Execution killed with signal 9
13 Runtime error 809 ms 131076 KB Execution killed with signal 9
14 Runtime error 832 ms 131076 KB Execution killed with signal 9
15 Runtime error 694 ms 131076 KB Execution killed with signal 9
16 Runtime error 708 ms 131076 KB Execution killed with signal 9
17 Runtime error 757 ms 131076 KB Execution killed with signal 9