Submission #799774

# Submission time Handle Problem Language Result Execution time Memory
799774 2023-08-01T01:39:54 Z Haidara Regions (IOI09_regions) C++17
85 / 100
2984 ms 119476 KB
/** * * * * * * * * * * * * * * * **\
 *                                 *
 *     Author: Haidara Nassour     *
 *  Coded in: YYYY\MM\DD HH:MM:SS  *
 *         Language: C++22         *
 *                                 *
\** * * * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
///#define int long long
#define itn int
#define endl '\n'
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define repf(i,x,n) for(int i=(x);(n);i++)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define max_heap(i) priority_queue< i >
#define min_heap(i) priority_queue< i , vector< i > ,greater< i > >
#define ff first
#define sinf(x) const int inf=x;
#define smaxn(x) const int maxn=x;
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pp push_back
#define mini(x,y) x=min(x,y)
#define maxi(x,y) x=max(x,y)
#define debug(x) cout<<endl<<#x<<"="<<x<<endl;
#define point(x) complex< x >
#define X real()
#define mp make_pair
#define Y imag()
#define add(x,y) x=(x+(y%mod))%mod
using namespace std;
using namespace __gnu_pbds;
void SIO(string name="",string name2="",string later="",string later2="")
{
    if(later=="")
    {
        later=".in";
        later2=".out";
    }
    else
    {
        if(later2=="")
            later2=later;
    }
    if(name!="")
    {
        if(name2=="")
            freopen((name+later).c_str(),"r",stdin);
        else
        {
            freopen((name+later).c_str(),"r",stdin);
            freopen((name2+later2).c_str(),"w",stdout);
        }
    }
}
template <class T> using o_set = tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using o_multiset = tree<T, null_type, less_equal<T>,rb_tree_tag, tree_order_statistics_node_update>;
///order_of_key = find index of element x ( returned val is integer )
///find_by_order = find value at index x ( returned val is pointer )
/// to swap s1 and s2 we make the following: s1.swap(s2)
template<class T> T chmin(T &a,T b)
{
    if(b<a)
        a=b;
    return a;
}
template<class T> T chmax(T &a,T b)
{
    if(a<b)
        a=b;
    return a;
}
template<class T> T mxmn(T &a,T &b)
{
    int mx=max(a,b);
    int mn=min(a,b);
    a=mx,b=mn;
    return mx+mn;
}
const double pi=2.0*acos(0.0);
const double memory=1048576.0;
const int inf=1LL<<50LL;
const int mod=1e9+7;
const int maxn=200002;
int n,R,cnt[25005],r[maxn];
int in[maxn],out[maxn];
int tim=1;
v(int)graph[maxn],em[25005],emofr[25005],id(25005,0);
void dfs(int st=1,int par=-1)
{
    in[st]=tim++;
    emofr[r[st]].pp(in[st]);
    em[r[st]].pp(st);
    for(auto i:graph[st])
    {
        if(i==par)
            continue;
        dfs(i,st);
    }
    out[st]=tim++;
}
int ans[300][25005];
void go(int col,int st=1,int cur=0,int par=-1)
{
    if(r[st]==col)
        cur++;
    else
        ans[id[col]][r[st]]+=cur;
    for(auto i:graph[st])
    {
        if(i==par)
            continue;
        go(col,i,cur,st);
    }
}
signed main()
{
    int q;
    cin>>n>>R>>q;
    cin>>r[1];
    cnt[r[1]]++;
    rep(i,2,n+1)
    {
        int j;
        cin>>j>>r[i];
        cnt[r[i]]++;
        graph[j].pp(i);
    }
    dfs();
    int cur_id=0;
    rep(i,1,R+1)
    if(cnt[i]>200)
        id[i]=cur_id++,go(i);
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(cnt[r1]>200)
            cout<<ans[id[r1]][r2]<<endl;
        else
        {
            int res=0;
            const auto &v=emofr[r2];
            for(auto i:em[r1])
            {
                res+=lower_bound(all(v),out[i])-upper_bound(all(v),in[i]);
            }
            cout<<res<<endl;
        }
        cout<<flush;
    }
}
/**
5 2
10
1
1 1
1 2
1 2
2 2
1 1

**/

Compilation message

regions.cpp:93:18: warning: overflow in conversion from 'long long int' to 'int' changes value from '1125899906842624' to '0' [-Woverflow]
   93 | const int inf=1LL<<50LL;
      |               ~~~^~~~~~
regions.cpp: In function 'void SIO(std::string, std::string, std::string, std::string)':
regions.cpp:59:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |             freopen((name+later).c_str(),"r",stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:62:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |             freopen((name+later).c_str(),"r",stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:63:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |             freopen((name2+later2).c_str(),"w",stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 6224 KB Output is correct
2 Correct 3 ms 6224 KB Output is correct
3 Correct 3 ms 6224 KB Output is correct
4 Correct 6 ms 6224 KB Output is correct
5 Correct 9 ms 6224 KB Output is correct
6 Correct 22 ms 6352 KB Output is correct
7 Correct 14 ms 6352 KB Output is correct
8 Correct 35 ms 6352 KB Output is correct
9 Correct 40 ms 6736 KB Output is correct
10 Correct 40 ms 6736 KB Output is correct
11 Correct 81 ms 7120 KB Output is correct
12 Correct 135 ms 7612 KB Output is correct
13 Correct 132 ms 7248 KB Output is correct
14 Correct 210 ms 7788 KB Output is correct
15 Correct 226 ms 11180 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 965 ms 11716 KB Output is correct
2 Correct 993 ms 10532 KB Output is correct
3 Correct 2341 ms 13344 KB Output is correct
4 Correct 234 ms 7936 KB Output is correct
5 Correct 304 ms 9544 KB Output is correct
6 Correct 475 ms 11116 KB Output is correct
7 Correct 1037 ms 12516 KB Output is correct
8 Correct 905 ms 20624 KB Output is correct
9 Correct 1730 ms 22260 KB Output is correct
10 Runtime error 709 ms 104172 KB Execution killed with signal 11
11 Runtime error 1456 ms 91160 KB Execution killed with signal 11
12 Correct 2984 ms 36328 KB Output is correct
13 Correct 2368 ms 37144 KB Output is correct
14 Correct 1870 ms 18948 KB Output is correct
15 Correct 2702 ms 22740 KB Output is correct
16 Runtime error 1033 ms 119476 KB Execution killed with signal 11
17 Correct 2415 ms 29924 KB Output is correct