oj.uz

Submission #1057142

# Submission time Handle Problem Language Result Execution time Memory
1057142 2024-08-13T14:30:56 Z Eliorita Regions (IOI09_regions) C++14
0 / 100
 65 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=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.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 16984 KB Time limit exceeded (wall clock)
7 Execution timed out 3 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 4 ms 25688 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 46424 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 57176 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 63064 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 75608 KB Time limit exceeded (wall clock)
15 Execution timed out 14 ms 99672 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 131072 KB Execution killed with signal 9
2 Runtime error 29 ms 131072 KB Execution killed with signal 9
3 Runtime error 23 ms 131072 KB Execution killed with signal 9
4 Execution timed out 12 ms 75864 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 92268 KB Time limit exceeded (wall clock)
6 Runtime error 21 ms 131072 KB Execution killed with signal 9
7 Runtime error 21 ms 131072 KB Execution killed with signal 9
8 Runtime error 46 ms 131072 KB Execution killed with signal 9
9 Runtime error 32 ms 131072 KB Execution killed with signal 9
10 Runtime error 50 ms 131072 KB Execution killed with signal 9
11 Runtime error 38 ms 131072 KB Execution killed with signal 9
12 Runtime error 40 ms 131072 KB Execution killed with signal 9
13 Runtime error 65 ms 131072 KB Execution killed with signal 9
14 Runtime error 41 ms 131072 KB Execution killed with signal 9
15 Runtime error 37 ms 131072 KB Execution killed with signal 9
16 Runtime error 36 ms 131072 KB Execution killed with signal 9
17 Runtime error 43 ms 131072 KB Execution killed with signal 9