oj.uz

답안 #799772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799772 2023-08-01T01:31:44 Z Haidara Regions (IOI09_regions) C++17
70 / 100
 2663 ms 103864 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[maxn],r[maxn];
int in[maxn],out[maxn];
int tim=1;
v(int)graph[maxn],em[maxn],emofr[maxn],id(maxn,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[25005/200+5][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[i].pp(j);
        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);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15184 KB Output is correct
2 Correct 7 ms 15184 KB Output is correct
3 Correct 8 ms 15184 KB Output is correct
4 Correct 11 ms 15184 KB Output is correct
5 Correct 14 ms 15184 KB Output is correct
6 Correct 20 ms 15184 KB Output is correct
7 Correct 28 ms 15224 KB Output is correct
8 Correct 38 ms 15312 KB Output is correct
9 Correct 42 ms 15696 KB Output is correct
10 Correct 67 ms 15684 KB Output is correct
11 Correct 97 ms 16024 KB Output is correct
12 Correct 126 ms 16464 KB Output is correct
13 Correct 161 ms 16540 KB Output is correct
14 Correct 213 ms 16976 KB Output is correct
15 Correct 279 ms 19940 KB Output is correct

Subtask #2
55.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1025 ms 20632 KB Output is correct
2 Runtime error 251 ms 41120 KB Execution killed with signal 11
3 Correct 2572 ms 22216 KB Output is correct
4 Correct 257 ms 17096 KB Output is correct
5 Correct 223 ms 18376 KB Output is correct
6 Correct 433 ms 20452 KB Output is correct
7 Correct 1022 ms 21872 KB Output is correct
8 Correct 940 ms 29452 KB Output is correct
9 Correct 1940 ms 31652 KB Output is correct
10 Runtime error 393 ms 88508 KB Execution killed with signal 11
11 Runtime error 1251 ms 81388 KB Execution killed with signal 11
12 Runtime error 1703 ms 70192 KB Execution killed with signal 11
13 Runtime error 1138 ms 72336 KB Execution killed with signal 11
14 Correct 1759 ms 29012 KB Output is correct
15 Correct 2663 ms 31660 KB Output is correct
16 Runtime error 569 ms 103864 KB Execution killed with signal 11
17 Correct 2402 ms 38816 KB Output is correct