oj.uz

Submission #895995

# Submission time Handle Problem Language Result Execution time Memory
895995 2023-12-31T11:46:35 Z Fucsdeptrai Regions (IOI09_regions) C++17
0 / 100
 61 ms 36400 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 8;
const int MOD = 998244353;

int n, r, q;
int a[N];
ll res[N];
int s[N], t[N], Timer;
vector<int> adj[N], vt[N];
vector<pair<int, int>> query[N];
vector<int> t1, t2;
ll vis[N];

void Dfs(int u = 1, int par = -1)
{
    s[u] = ++ Timer;
    for(int v : adj[u])
    {
        if(v == par) continue;
        Dfs(v, u);
    }
    t[u] = Timer;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
/*
    freopen("men-graph.inp", "r", stdin);
    freopen("men-graph.out", "w", stdout);
*/
    memset(vis, -1, sizeof vis);

    cin >> n >> r >> q;
    cin >> a[1];
    vt[a[1]].push_back(1);

    for(int i = 2;i <= n;i ++)
    {
        int j;
        cin >> a[i] >> j;
        vt[j].push_back(i);
        adj[i].push_back(a[i]);
        adj[a[i]].push_back(i);
    }

    Dfs();

    for(int i = 1;i <= q;i ++)
    {
        int u, v; cin >> u >> v;
        if(vt[u].size() > vt[v].size())
        {
            query[u].push_back({v, i});
        }
        else
        {
            query[v].push_back({-u, i});
        }
    }

    for(int u = 1; u <= n;u ++)
    {
        t1.clear(); t2.clear();
        for(int v : vt[u])
        {
            t1.push_back(s[v]);
            t2.push_back(t[v]);
        }
        sort(t1.begin(), t1.end());
        sort(t2.begin(), t2.end());
        sort(query[u].begin(), query[u].end());
        int lastv = 0, lastid = -1;
        for(auto [v, id] : query[u])
        {
            if(lastv == v)
            {
                res[id] = res[lastid];
                continue;
            }
            lastv = v;
            lastid = id;
            if(v < 0)
            {
                v = -v;
                for(int i : vt[v])
                {
                    int l = lower_bound(t1.begin(), t1.end(), s[i]) - t1.begin();
                    int r = upper_bound(t1.begin(), t1.end(), t[i]) - t1.begin();
                    if(t1[l] > t[i]) continue;
                    res[id] += (r - l);
                }
            }
            else
            {
                for(int i : vt[v])
                {
                    int l = upper_bound(t2.begin(), t2.end(), s[i] - 1) - t2.begin();
                    int r = upper_bound(t1.begin(), t1.end(), s[i]) - t1.begin();
                    if(l >= r) continue;
                    res[id] += (r - l);
                }
            }
        }
    }

    for(int i = 1; i <= q;i ++)
    {
        cout << res[i] << '\n';
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 17236 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 16984 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 17496 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 17240 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 17496 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 17932 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 17956 KB Time limit exceeded (wall clock)
14 Execution timed out 9 ms 18264 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 22564 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 19 ms 22800 KB Time limit exceeded (wall clock)
2 Execution timed out 20 ms 22448 KB Time limit exceeded (wall clock)
3 Execution timed out 21 ms 24156 KB Time limit exceeded (wall clock)
4 Execution timed out 11 ms 18244 KB Time limit exceeded (wall clock)
5 Execution timed out 11 ms 19776 KB Time limit exceeded (wall clock)
6 Execution timed out 18 ms 21364 KB Time limit exceeded (wall clock)
7 Execution timed out 19 ms 22288 KB Time limit exceeded (wall clock)
8 Execution timed out 27 ms 26552 KB Time limit exceeded (wall clock)
9 Execution timed out 42 ms 26324 KB Time limit exceeded (wall clock)
10 Execution timed out 44 ms 30476 KB Time limit exceeded (wall clock)
11 Execution timed out 59 ms 27932 KB Time limit exceeded (wall clock)
12 Execution timed out 61 ms 27052 KB Time limit exceeded (wall clock)
13 Execution timed out 49 ms 27812 KB Time limit exceeded (wall clock)
14 Execution timed out 59 ms 27704 KB Time limit exceeded (wall clock)
15 Execution timed out 53 ms 30700 KB Time limit exceeded (wall clock)
16 Execution timed out 60 ms 36400 KB Time limit exceeded (wall clock)
17 Execution timed out 56 ms 35132 KB Time limit exceeded (wall clock)