Submission #1057142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057142		Eliorita	Regions (IOI09_regions)	C++14	0 / 100	65 ms	131072 KiB

regions

#include<bits/stdc++.h>
#define x first
#define y second
#define N 200010
using namespace std;
typedef pair<int,int> ii;
int magic=500;
int n,q,r,cnt,num[N],tail[N];
int h[N],reg[N];
int cur[N][500];
int dom[25001][500],heavy[N],rev[N],big;
vector<int> g[N];
vector<int> st[N];
void dfs(int u,int pre)
{
    num[u]=++cnt;
    st[h[u]].push_back(u);
    for(int v : g[u])
    {
        if(v==pre) continue;
        dfs(v,u);
        for(int i=1;i<=big;i++)
        {
            cur[u][i]+=cur[v][i];
            dom[h[u]][i]+=cur[v][i];
        }
    }
    tail[u]=cnt;
}
void init()
{
    for(int i=1;i<=n;i++) reg[h[i]]++;
    for(int i=1;i<=r;i++)
    {
        if(reg[i]>=magic)
        {
            heavy[++big]=i;
            rev[i]=big;
        }
    }
    assert(big<=447);
    for(int i=1;i<=n;i++) cur[i][rev[h[i]]]++;
}
vector<int> tmp,res;
struct greaters
{
    bool operator()(const int& a, const int& b) const
    {
        return num[a] < num[b];
    }
};
bool inside(int u,int v)
{
    return num[u]>=num[v]&&num[u]<=tail[v];
}
int solve(int r1,int r2)
{
    int ans=0,cur=0;
    res.clear();
    tmp.clear();
    merge(st[r1].begin(),st[r1].end(),st[r2].begin(),st[r2].end(),back_inserter(tmp),greaters());
    for(int u : tmp)
    {
        while(res.size()&&!inside(u,res.back()))
        {
            cur-=(h[res.back()]==r2);
            res.pop_back();
        }
        if(h[u]==r2)
        {
            ans+=res.size()-cur;
            cur++;
        }
        res.push_back(u);
    }
    return ans;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>r>>q;
    cin>>h[1];
    for(int i=2;i<=n;i++)
    {
        int u; cin>>u>>h[i];
        g[u].push_back(i);
        g[i].push_back(u);
    }
    init();
    dfs(1,0);
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(reg[r2]>=magic) cout<<dom[r1][rev[r2]]<<'\n';
        else cout<<solve(r1,r2)<<'\n';
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85