oj.uz

Submission #1057172

# Submission time Handle Problem Language Result Execution time Memory
1057172 2024-08-13T14:42:16 Z Eliorita Regions (IOI09_regions) C++14
0 / 100
 57 ms 131072 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define N 200010
using namespace std;
typedef pair<int,int> ii;
int magic=400;
int n,q,r,cnt,num[N],tail[N];
int h[N],reg[N];
int cur[N][501];
int dom[N][501],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;
        }
    }
    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[r1]<magic&&reg[r2]<magic) cout<<solve(r1,r2)<<'\n';
        else cout<<dom[r1][rev[r2]]<<'\n';
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 16984 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 16984 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 16984 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 16984 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 16984 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 19028 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 19032 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 21080 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 27736 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 35928 KB Time limit exceeded (wall clock)
11 Execution timed out 8 ms 46168 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 56920 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 65076 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 77656 KB Time limit exceeded (wall clock)
15 Execution timed out 17 ms 99568 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 131072 KB Execution killed with signal 9
2 Runtime error 22 ms 131072 KB Execution killed with signal 9
3 Runtime error 42 ms 131072 KB Execution killed with signal 9
4 Execution timed out 12 ms 77656 KB Time limit exceeded (wall clock)
5 Execution timed out 18 ms 92248 KB Time limit exceeded (wall clock)
6 Runtime error 19 ms 131072 KB Execution killed with signal 9
7 Runtime error 27 ms 131072 KB Execution killed with signal 9
8 Runtime error 24 ms 131072 KB Execution killed with signal 9
9 Runtime error 30 ms 131072 KB Execution killed with signal 9
10 Runtime error 32 ms 131072 KB Execution killed with signal 9
11 Runtime error 36 ms 131072 KB Execution killed with signal 9
12 Runtime error 55 ms 131072 KB Execution killed with signal 9
13 Runtime error 35 ms 131072 KB Execution killed with signal 9
14 Runtime error 47 ms 131072 KB Execution killed with signal 9
15 Runtime error 36 ms 131072 KB Execution killed with signal 9
16 Runtime error 57 ms 131072 KB Execution killed with signal 9
17 Runtime error 35 ms 131072 KB Execution killed with signal 9