oj.uz

Submission #1083726

# Submission time Handle Problem Language Result Execution time Memory
1083726 2024-09-03T22:17:09 Z rayan_bd Regions (IOI09_regions) C++17
9 / 100
 8000 ms 68220 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 LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
 *
 *
    ================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 [x,y]:a.regions)
            ans.regions[x]+=y;
        for(auto [x,y]:b.regions)
            ans.regions[x]+=y;
        return ans;
    }
    void update(int node,int st,int dr,int pos,int region)
    {
        if(st==dr)
        {
 
            tree[node].regions[region]++;
            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);
 
        tree[node]=combine(tree[2*node],tree[2*node+1]);
    }
 
    item query(int node,int st,int dr,int L,int R)
    {
        if(st>R || dr<L)
        {
            return neutru;
        }
        if(L<=st && dr<=R)
        {
            return tree[node];
        }
        int mid=(st+dr)/2;
        item left=query(2*node,st,mid,L,R);
        item right=query(2*node+1,mid+1,dr,L,R);
        return combine(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).regions[region];
        return ans;
    }
    void check()
    {
        for(auto [x,y]:tree[1].regions)
        {
            cout<<x<<" "<<y<<nl;
        }
    }
};
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;
}

Compilation message

regions.cpp:8: warning: "LLONG_MAX" redefined
    8 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from regions.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      |

Subtask #1
9.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8792 KB Output is correct
2 Correct 4 ms 8740 KB Output is correct
3 Correct 5 ms 8792 KB Output is correct
4 Correct 11 ms 8788 KB Output is correct
5 Correct 78 ms 9168 KB Output is correct
6 Correct 414 ms 9484 KB Output is correct
7 Correct 488 ms 10064 KB Output is correct
8 Correct 1018 ms 10204 KB Output is correct
9 Execution timed out 8041 ms 12460 KB Time limit exceeded
10 Correct 6789 ms 15924 KB Output is correct
11 Execution timed out 8045 ms 18752 KB Time limit exceeded
12 Execution timed out 8042 ms 23120 KB Time limit exceeded
13 Execution timed out 8064 ms 25168 KB Time limit exceeded
14 Execution timed out 8045 ms 27984 KB Time limit exceeded
15 Execution timed out 8045 ms 36820 KB Time limit exceeded

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8029 ms 43064 KB Time limit exceeded
2 Execution timed out 8077 ms 42200 KB Time limit exceeded
3 Execution timed out 8039 ms 45136 KB Time limit exceeded
4 Execution timed out 8005 ms 21388 KB Time limit exceeded
5 Execution timed out 8045 ms 24384 KB Time limit exceeded
6 Execution timed out 8073 ms 26164 KB Time limit exceeded
7 Execution timed out 8038 ms 30192 KB Time limit exceeded
8 Execution timed out 8054 ms 40272 KB Time limit exceeded
9 Execution timed out 8039 ms 48464 KB Time limit exceeded
10 Execution timed out 8029 ms 57568 KB Time limit exceeded
11 Execution timed out 8057 ms 60112 KB Time limit exceeded
12 Execution timed out 8105 ms 57548 KB Time limit exceeded
13 Execution timed out 8044 ms 57680 KB Time limit exceeded
14 Execution timed out 8034 ms 59776 KB Time limit exceeded
15 Execution timed out 8080 ms 62800 KB Time limit exceeded
16 Execution timed out 8038 ms 68220 KB Time limit exceeded
17 Execution timed out 8026 ms 67112 KB Time limit exceeded