oj.uz

Submission #913916

# Submission time Handle Problem Language Result Execution time Memory
913916 2024-01-20T13:38:14 Z VMaksimoski008 Regions (IOI09_regions) C++14
30 / 100
 1645 ms 99224 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;
short home[maxn];
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--) {
            int r1, r2, ans = 0;
            cin >> r1 >> r2;
 
            for(int &x : by_home[r1])
                ans += dp[r2][x];
        
            cout << ans << '\n';
            cout.flush();
        }
        return 0;
    }

    int mx = *max_element(cnt.begin(), cnt.end());

    if(mx <= 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--) {
            int r1, r2, ans = 0;
            cin >> r1 >> r2;

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

            cout << ans << '\n';
            cout.flush();
        }
    }
 
    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 344 KB Output is correct
3 Correct 1 ms 344 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 14 ms 1368 KB Output is correct
8 Correct 14 ms 2136 KB Output is correct
9 Correct 29 ms 6648 KB Output is correct
10 Correct 78 ms 17744 KB Output is correct
11 Correct 86 ms 17240 KB Output is correct
12 Correct 120 ms 37200 KB Output is correct
13 Correct 221 ms 33704 KB Output is correct
14 Correct 140 ms 25688 KB Output is correct
15 Correct 244 ms 42924 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 65140 KB Output is correct
2 Correct 1398 ms 74580 KB Output is correct
3 Correct 1645 ms 99224 KB Output is correct
4 Runtime error 7 ms 3512 KB Execution killed with signal 11
5 Runtime error 11 ms 4880 KB Execution killed with signal 11
6 Runtime error 12 ms 5816 KB Execution killed with signal 11
7 Runtime error 15 ms 7776 KB Execution killed with signal 11
8 Runtime error 21 ms 12088 KB Execution killed with signal 11
9 Runtime error 33 ms 17304 KB Execution killed with signal 11
10 Runtime error 43 ms 20348 KB Execution killed with signal 11
11 Runtime error 48 ms 18388 KB Execution killed with signal 11
12 Incorrect 35 ms 11104 KB Unexpected end of file - int32 expected
13 Incorrect 32 ms 10876 KB Unexpected end of file - int32 expected
14 Incorrect 40 ms 10856 KB Unexpected end of file - int32 expected
15 Incorrect 43 ms 11808 KB Unexpected end of file - int32 expected
16 Incorrect 43 ms 11988 KB Unexpected end of file - int32 expected
17 Incorrect 43 ms 12264 KB Unexpected end of file - int32 expected