oj.uz

Submission #409448

# Submission time Handle Problem Language Result Execution time Memory
409448 2021-05-20T18:49:28 Z ivycube Regions (IOI09_regions) C++14
0 / 100
 936 ms 32396 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, a[N], ord, st[N], ed[N];
vector<int> adj[N], region[R], large_region;
vector<vector<int>> large_r1, large_r2;
map<int, int> region_idx;

void dfs(int u) {
    st[u] = ++ord;
    for (auto v : adj[u]) dfs(v);
    ed[u] = ord;
}

inline bool cmp(const int &a, const int &b) {
    return st[a] < st[b];
}

void dfs1(int u, int r1, int cnt = 0) {
    cnt += (a[u] == r1);
    large_r1[region_idx[r1]][a[u]] += cnt; // count all employee in subtree for r1
    for (auto v : adj[u]) dfs1(v, r1, cnt);
}

int dfs2(int u, int r2) {
    int cnt = (a[u] == r2);     // count all ancestors for r2
    for (auto v : adj[u]) cnt += dfs2(v, r2);
    large_r2[region_idx[r2]][a[u]] += cnt;
    return cnt;
}

void calc_large() {
    large_r1.resize((int)large_region.size() + 1, vector<int>(k + 1, 0));
    large_r2.resize((int)large_region.size() + 1, vector<int>(k + 1, 0));
    int idx = 0;
    for (auto r : large_region) {
        region_idx[r] = ++idx;
        dfs1(1, r);
        dfs2(1, r);
    }
}

inline bool ancestor_of(const int &a, const int &b) {
    return st[a] <= st[b] && ed[b] <= ed[a];
}

int calc(int r1, int r2) {
    vector<int> blocks(region[r1].begin(), region[r1].end());
    blocks.insert(blocks.end(), region[r2].begin(), region[r2].end());
    sort(blocks.begin(), blocks.end(), cmp);
    
    int res = 0;
    vector<int> stk;
    for (auto u : blocks) {
        while(!stk.empty() && !ancestor_of(stk.back(), u)) stk.pop_back();
        if (a[u] == r1) stk.push_back(u);
        else res += (int) stk.size();
    }
    return res;
}

int main() {
    scanf("%d%d%d", &n, &k, &m);
    scanf("%d", &a[1]);
    region[a[1]].push_back(1);
    
    int j;
    for (int i = 2; i <= n; i++) {
        scanf("%d%d", &j, &a[i]);
        adj[j].push_back(i);
        region[a[i]].push_back(i);
    }
    
    dfs(1);
    for (int i = 1; i <= k; i++) {
        sort(region[i].begin(), region[i].end(), cmp);
        if (region[i].size() > UP) large_region.push_back(i);
    }
    
    calc_large();
    
    int r1, r2;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &r1, &r2);
        if (region[r1].size() > UP)
            printf("%d\n", large_r1[region_idx[r1]][r2]);
        else if (region[r2].size() > UP)
            printf("%d\n", large_r2[region_idx[r2]][r1]);
        else
            printf("%d\n", calc(r1, r2));
    }
    
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d%d%d", &n, &k, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d", &a[1]);
      |     ~~~~~^~~~~~~~~~~~~
regions.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d%d", &j, &a[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d%d", &r1, &r2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 113 ms 10260 KB Time limit exceeded (wall clock)
2 Execution timed out 107 ms 8672 KB Time limit exceeded (wall clock)
3 Execution timed out 80 ms 12596 KB Time limit exceeded (wall clock)
4 Execution timed out 16 ms 6984 KB Time limit exceeded (wall clock)
5 Execution timed out 18 ms 8136 KB Time limit exceeded (wall clock)
6 Execution timed out 271 ms 11592 KB Time limit exceeded (wall clock)
7 Execution timed out 114 ms 10176 KB Time limit exceeded (wall clock)
8 Execution timed out 750 ms 23872 KB Time limit exceeded (wall clock)
9 Execution timed out 76 ms 13520 KB Time limit exceeded (wall clock)
10 Execution timed out 759 ms 31680 KB Time limit exceeded (wall clock)
11 Execution timed out 96 ms 13392 KB Time limit exceeded (wall clock)
12 Execution timed out 181 ms 15636 KB Time limit exceeded (wall clock)
13 Execution timed out 146 ms 16192 KB Time limit exceeded (wall clock)
14 Execution timed out 936 ms 18624 KB Time limit exceeded (wall clock)
15 Execution timed out 136 ms 21824 KB Time limit exceeded (wall clock)
16 Execution timed out 122 ms 31092 KB Time limit exceeded (wall clock)
17 Execution timed out 422 ms 32396 KB Time limit exceeded (wall clock)