Submission #895995

#	Time	Username	Problem	Language	Result	Execution time	Memory
895995		Fucsdeptrai	Regions (IOI09_regions)	C++17	0 / 100	61 ms	36400 KiB

regions

#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
• Subtask 2: 0 / 85