oj.uz

Submission #1083727

# Submission time Handle Problem Language Result Execution time Memory
1083727 2024-09-03T22:20:58 Z rayan_bd Regions (IOI09_regions) C++17
13 / 100
 2650 ms 131072 KB 
#include <bits/stdc++.h>
#define NMAX 200001
#define pb push_back
#define eb emplace_back
#define MOD 100003
#define nl '\n'
#define INF  2147483647
#define pii pair<int,int>
#define tpl tuple<int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
/*
 *
 *
    ================DEMONSTRATION===================
 
 
    =====================END========================
 */
struct item{
    map<int,int>regions;
};
class segtree{
private:
    int n;
    vector<item>tree;
public:
    void init(int sz)
    {
        n=sz;
        tree.resize(4*sz+1);
    }
    item neutru;
    item combine(item a,item b)
    {
        item ans;
        for(auto it:a.regions)
            ans.regions[it.first]+=it.second;
        for(auto it:b.regions)
            ans.regions[it.first]+=it.second;
        return ans;
    }
    void update(int node,int st,int dr,int pos,int region)
    {
    	tree[node].regions[region]++;
        if(st==dr)
        {
            
            return;
        }
        int mid=(st+dr)/2;
        if(pos<=mid)
            update(2*node,st,mid,pos,region);
        else
            update(2*node+1,mid+1,dr,pos,region);
    }
 
    int query(int node,int st,int dr,int L,int R,int X)
    {
        if(st>R || dr<L)
        {
            return 0;
        }
        if(L<=st && dr<=R)
        {
            return tree[node].regions[X];
        }
        int mid=(st+dr)/2;
        int left=query(2*node,st,mid,L,R,X);
        int right=query(2*node+1,mid+1,dr,L,R,X);
        return left+right;
    }
 
    void update(int pos,int region)
    {
        update(1,1,n,pos,region);
    }
    int query(int L,int R,int region)
    {
        int ans=query(1,1,n,L,R,region);
        return ans;
    }
};
int n,r,q;
int r1,r2,ans;
vector<int>h(NMAX),s(NMAX);
vector<int>tin(NMAX),tout(NMAX);
vector<vector<int>>G(NMAX);
vector<vector<int>>R(25001);
int timp;
void read_query()
{
    cin>>r1>>r2;
}
void print_query()
{
    cout.flush()<<ans<<nl;
    cout.flush();
}
void dfs(int node,int parent)
{
    tin[node]=++timp;
    for(auto x:G[node])
    {
        if(x!=parent)
            dfs(x,node);
    }
    tout[node]=timp;
}
segtree seg;
signed main() {
 


    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin>>n>>r>>q;
    cin>>h[1];
    R[h[1]].pb(1);
    for(int i=2;i<=n;++i)
    {
        cin>>s[i]>>h[i];
        R[h[i]].pb(i);
        G[i].pb(s[i]);
        G[s[i]].pb(i);
    }
 
    dfs(1,-1);
 
    seg.init(n);
    for(int i=1;i<=n;++i)
    {
        seg.update(tin[i],h[i]);
    }
//    seg.check();
    while(q--)
    {
        ans=0;
        read_query();
        for(auto x:R[r1])
        {
            int aux=seg.query(tin[x],tout[x],r2);
            ans+=(aux);
        }
        print_query();
    }
 
    return 0;
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8792 KB Output is correct
2 Correct 4 ms 8840 KB Output is correct
3 Correct 5 ms 8940 KB Output is correct
4 Correct 6 ms 9048 KB Output is correct
5 Correct 12 ms 9560 KB Output is correct
6 Correct 25 ms 10312 KB Output is correct
7 Correct 39 ms 12624 KB Output is correct
8 Correct 61 ms 14196 KB Output is correct
9 Correct 127 ms 22864 KB Output is correct
10 Correct 276 ms 38996 KB Output is correct
11 Correct 1083 ms 74928 KB Output is correct
12 Correct 1412 ms 91240 KB Output is correct
13 Correct 1051 ms 100992 KB Output is correct
14 Runtime error 1721 ms 131072 KB Execution killed with signal 9
15 Runtime error 1561 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1010 ms 131072 KB Execution killed with signal 9
2 Runtime error 1016 ms 131072 KB Execution killed with signal 9
3 Runtime error 1146 ms 131072 KB Execution killed with signal 9
4 Runtime error 1369 ms 131072 KB Execution killed with signal 9
5 Runtime error 1653 ms 131072 KB Execution killed with signal 9
6 Runtime error 2650 ms 131072 KB Execution killed with signal 9
7 Runtime error 2354 ms 131072 KB Execution killed with signal 9
8 Runtime error 719 ms 131072 KB Execution killed with signal 9
9 Runtime error 473 ms 131072 KB Execution killed with signal 9
10 Runtime error 383 ms 131072 KB Execution killed with signal 9
11 Runtime error 477 ms 131072 KB Execution killed with signal 9
12 Runtime error 497 ms 131072 KB Execution killed with signal 9
13 Runtime error 438 ms 131072 KB Execution killed with signal 9
14 Runtime error 475 ms 131072 KB Execution killed with signal 9
15 Runtime error 383 ms 131072 KB Execution killed with signal 9
16 Runtime error 322 ms 131072 KB Execution killed with signal 9
17 Runtime error 366 ms 131072 KB Execution killed with signal 9