oj.uz

Submission #409257

# Submission time Handle Problem Language Result Execution time Memory
409257 2021-05-20T12:54:51 Z ivycube Regions (IOI09_regions) C++14
0 / 100
 70 ms 13248 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>

using namespace std;
using PII = pair<int, int>;

const int N = 200005, R = 25005, UP = 450 /*threshold*/;

int n, m, k, region[N], sz[R], ans[N], cnt[R];;
map<PII, int> qtoi;
vector<int> adj[N];
vector<PII> lookdown[R], lookup[R];

void dfs1(int u) {
    int r1 = region[u];
    for (auto p : lookdown[r1]) {
        int qid = p.second, r2 = p.first;
        ans[qid] -= cnt[r2];
    }
    cnt[r1] ++ ;
    for (auto v : adj[u]) dfs1(v);
    for (auto p : lookdown[r1]) {
        int qid = p.second, r2 = p.first;
        ans[qid] += cnt[r2];
    }
}

void dfs2(int u) {
    int r2 = region[u];
    cnt[r2] ++ ;
    for (auto p : lookup[r2]) {
        int qid = p.second, r1 = p.first;
        ans[qid] += cnt[r1];
    }
    for (auto v : adj[u]) dfs2(v);
    cnt[r2] -- ;
}

int main() {
    scanf("%d%d%d", &n, &k, &m);
    scanf("%d", &region[1]);
    sz[region[1]] ++ ;
    
    int j, r;
    for (int i = 2; i <= n; i++) {
        scanf("%d%d", &j, &r);
        adj[j].push_back(i);
        region[i] = r;
        sz[r] ++ ;
    }
    
    int a, b;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &a, &b);
        if (qtoi[{a, b}]) {
            ans[i] = -qtoi[{a, b}];
            continue;
        }
        qtoi[{a, b}] = i;
        
        if (sz[b] >= UP) lookdown[a].push_back({b, i});
        else lookup[b].push_back({a, i});
    }
    
    dfs1(1);
    memset(cnt, 0, sizeof cnt);
    dfs2(1);
    
    for (int i = 1; i <= m; i++) {
        if (ans[i] < 0) ans[i] = ans[-ans[i]];
        printf("%d\n", ans[i]);
    }
    
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d%d", &n, &k, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d", &region[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d%d", &j, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 6072 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
8 Execution timed out 5 ms 6216 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 6344 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 6472 KB Time limit exceeded (wall clock)
11 Execution timed out 8 ms 6600 KB Time limit exceeded (wall clock)
12 Execution timed out 10 ms 6856 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 6600 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 7112 KB Time limit exceeded (wall clock)
15 Execution timed out 14 ms 7496 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25 ms 8640 KB Time limit exceeded (wall clock)
2 Execution timed out 27 ms 8020 KB Time limit exceeded (wall clock)
3 Execution timed out 30 ms 9212 KB Time limit exceeded (wall clock)
4 Execution timed out 17 ms 6984 KB Time limit exceeded (wall clock)
5 Execution timed out 16 ms 7372 KB Time limit exceeded (wall clock)
6 Execution timed out 19 ms 7684 KB Time limit exceeded (wall clock)
7 Execution timed out 26 ms 8228 KB Time limit exceeded (wall clock)
8 Execution timed out 33 ms 9664 KB Time limit exceeded (wall clock)
9 Execution timed out 51 ms 11072 KB Time limit exceeded (wall clock)
10 Execution timed out 53 ms 12096 KB Time limit exceeded (wall clock)
11 Execution timed out 70 ms 10560 KB Time limit exceeded (wall clock)
12 Execution timed out 57 ms 12768 KB Time limit exceeded (wall clock)
13 Execution timed out 61 ms 12224 KB Time limit exceeded (wall clock)
14 Execution timed out 61 ms 12112 KB Time limit exceeded (wall clock)
15 Execution timed out 61 ms 13168 KB Time limit exceeded (wall clock)
16 Execution timed out 62 ms 13248 KB Time limit exceeded (wall clock)
17 Execution timed out 60 ms 13248 KB Time limit exceeded (wall clock)