oj.uz

Submission #526464

# Submission time Handle Problem Language Result Execution time Memory
526464 2022-02-14T20:21:45 Z PiejanVDC Regions (IOI09_regions) C++17
19 / 100
 8000 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int>top;
vector<int>adj[(int)2e5+5];
vector<int>region;

map<pair<int,int>,int>mp;

void dfs(int u, int e = -1) {
    for(auto z : top) {
        mp[{region[u],region[z]}]++;
    }
    top.push_back(u);
    for(auto z : adj[u]) if(z != e) {
        dfs(z,u);
    }
    top.pop_back();
}

signed main() {
    int n,r,q; cin>>n>>r>>q;
    region.resize(n);
    int h; cin>>h; region[0] = h;
    for(int i = 1 ; i < n ; i++) {
        int s,h; cin>>s>>h;
        s--;
        adj[s].push_back(i);
        region[i] = h;
    }
    dfs(0);
    while(q--) {
        int a,b; cin>>a>>b;
        cout << flush << mp[{b,a}] << "\n";
    }
    return 0;
}

Subtask #1
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 6 ms 4936 KB Output is correct
5 Correct 12 ms 5064 KB Output is correct
6 Correct 49 ms 8324 KB Output is correct
7 Correct 37 ms 6124 KB Output is correct
8 Correct 43 ms 7076 KB Output is correct
9 Correct 952 ms 11184 KB Output is correct
10 Correct 191 ms 13120 KB Output is correct
11 Correct 441 ms 10212 KB Output is correct
12 Correct 3291 ms 18788 KB Output is correct
13 Correct 232 ms 10472 KB Output is correct
14 Correct 602 ms 8408 KB Output is correct
15 Execution timed out 8055 ms 11592 KB Time limit exceeded

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8037 ms 10988 KB Time limit exceeded
2 Correct 6197 ms 10008 KB Output is correct
3 Execution timed out 8042 ms 14020 KB Time limit exceeded
4 Runtime error 1834 ms 131076 KB Execution killed with signal 9
5 Runtime error 2327 ms 131076 KB Execution killed with signal 9
6 Runtime error 1307 ms 131076 KB Execution killed with signal 9
7 Runtime error 730 ms 131076 KB Execution killed with signal 9
8 Runtime error 2308 ms 131076 KB Execution killed with signal 9
9 Runtime error 1036 ms 131076 KB Execution killed with signal 9
10 Runtime error 2573 ms 131076 KB Execution killed with signal 9
11 Runtime error 1480 ms 131076 KB Execution killed with signal 9
12 Runtime error 1531 ms 131076 KB Execution killed with signal 9
13 Runtime error 1295 ms 131076 KB Execution killed with signal 9
14 Runtime error 1333 ms 131076 KB Execution killed with signal 9
15 Runtime error 1303 ms 131076 KB Execution killed with signal 9
16 Runtime error 1406 ms 131076 KB Execution killed with signal 9
17 Runtime error 1462 ms 131076 KB Execution killed with signal 9