oj.uz

Submission #913919

# Submission time Handle Problem Language Result Execution time Memory
913919 2024-01-20T13:43:41 Z VMaksimoski008 Regions (IOI09_regions) C++14
30 / 100
 1806 ms 99232 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int maxn = 2e5 + 5;
 
void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
int n, r, q, i, in[maxn], out[maxn], timer = 0, ans = 0;
short home[maxn], r1, r2;
vector<vector<int> > graph, dp;
 
void dfs(int u) {
    dp[home[u]][u]++;
 
    for(int &v : graph[u]) {
        dfs(v);
        for(i=1; i<=r; i++)
            dp[i][u] += dp[i][v];
    }
}

void dfs2(int u) {
    in[u] = timer++;
    for(int &v : graph[u])
        dfs(v);
    out[u] = timer;
}

bool anc(int u, int v) { return (in[u] <= in[v] && out[u] >= out[v]); }
 
int32_t main() {
    setIO();
 
    cin >> n >> r >> q;
    graph.resize(n+1);
    vector<int> cnt(r+1);
 
    cin >> home[1];
    cnt[home[1]]++;
 
    for(i=2; i<=n; i++) {
        int p;
        cin >> p >> home[i];
        cnt[home[i]]++;
        graph[p].push_back(i);
    }
 
    if(r <= 500) {
        dp.resize(r+1, vector<int>(n+1));
        dfs(1);
 
        vector<vector<int> > by_home(r+1);
        for(i=1; i<=n; i++)
            by_home[home[i]].push_back(i);
 
        while(q--) {
            ans = 0;
            cin >> r1 >> r2;
 
            for(int &x : by_home[r1])
                ans += dp[r2][x];
        
            cout << ans << endl;
        }
        return 0;
    }

    if(*max_element(cnt.begin(), cnt.end()) <= 500) {
        dfs2(1);

        vector<vector<int> > by_home(r+1);
        for(i=1; i<=n; i++)
            by_home[home[i]].push_back(i);

        while(q--) {
            ans = 0;
            cin >> r1 >> r2;

            for(int &u : by_home[r1])
                for(int &v : by_home[r2]) ans += anc(u, v);

            cout << ans << endl;
        }
    }
 
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 9 ms 1112 KB Output is correct
7 Correct 12 ms 1368 KB Output is correct
8 Correct 15 ms 2136 KB Output is correct
9 Correct 31 ms 6744 KB Output is correct
10 Correct 60 ms 17496 KB Output is correct
11 Correct 82 ms 17240 KB Output is correct
12 Correct 116 ms 37200 KB Output is correct
13 Correct 215 ms 33644 KB Output is correct
14 Correct 146 ms 26016 KB Output is correct
15 Correct 269 ms 42924 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 65144 KB Output is correct
2 Correct 1487 ms 74580 KB Output is correct
3 Correct 1806 ms 99232 KB Output is correct
4 Runtime error 8 ms 3672 KB Execution killed with signal 11
5 Runtime error 10 ms 4760 KB Execution killed with signal 11
6 Runtime error 12 ms 5972 KB Execution killed with signal 11
7 Runtime error 17 ms 7760 KB Execution killed with signal 11
8 Runtime error 22 ms 12184 KB Execution killed with signal 11
9 Runtime error 38 ms 17228 KB Execution killed with signal 11
10 Runtime error 38 ms 20176 KB Execution killed with signal 11
11 Runtime error 56 ms 18268 KB Execution killed with signal 11
12 Incorrect 35 ms 11204 KB Unexpected end of file - int32 expected
13 Incorrect 33 ms 10620 KB Unexpected end of file - int32 expected
14 Incorrect 37 ms 10976 KB Unexpected end of file - int32 expected
15 Incorrect 46 ms 11852 KB Unexpected end of file - int32 expected
16 Incorrect 45 ms 12092 KB Unexpected end of file - int32 expected
17 Incorrect 40 ms 11928 KB Unexpected end of file - int32 expected