oj.uz

답안 #799770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799770 2023-08-01T01:17:32 Z Haidara Regions (IOI09_regions) C++17
90 / 100
 3034 ms 131072 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=200100;
int n,R,cnt[maxn],r[maxn];
int in[maxn],out[maxn];
int tim=1;
v(int)graph[maxn],em[maxn],emofr[maxn];
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++;
}
m(int,int)ans[maxn];
void go(int col,int st=1,int cur=0,int par=-1)
{
    if(r[st]==col)
        cur++;
    else 
        ans[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();
    rep(i,1,R+1)
    if(cnt[i]>300)
        go(i);
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(cnt[r1]>300)
            cout<<ans[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 11 ms 23760 KB Output is correct
2 Correct 10 ms 23760 KB Output is correct
3 Correct 12 ms 23760 KB Output is correct
4 Correct 12 ms 23760 KB Output is correct
5 Correct 17 ms 23760 KB Output is correct
6 Correct 28 ms 23888 KB Output is correct
7 Correct 36 ms 23888 KB Output is correct
8 Correct 34 ms 23888 KB Output is correct
9 Correct 47 ms 24276 KB Output is correct
10 Correct 69 ms 24340 KB Output is correct
11 Correct 113 ms 24556 KB Output is correct
12 Correct 139 ms 25052 KB Output is correct
13 Correct 165 ms 25192 KB Output is correct
14 Correct 210 ms 25476 KB Output is correct
15 Correct 234 ms 27828 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1609 ms 29036 KB Output is correct
2 Correct 1605 ms 28360 KB Output is correct
3 Correct 2047 ms 31360 KB Output is correct
4 Correct 213 ms 25680 KB Output is correct
5 Correct 332 ms 27056 KB Output is correct
6 Correct 706 ms 44484 KB Output is correct
7 Correct 1430 ms 51436 KB Output is correct
8 Correct 1741 ms 81968 KB Output is correct
9 Correct 2388 ms 64484 KB Output is correct
10 Runtime error 1563 ms 131072 KB Execution killed with signal 9
11 Runtime error 2467 ms 131072 KB Execution killed with signal 9
12 Correct 960 ms 35940 KB Output is correct
13 Correct 1562 ms 37192 KB Output is correct
14 Correct 2140 ms 53528 KB Output is correct
15 Correct 2679 ms 43428 KB Output is correct
16 Correct 2503 ms 52428 KB Output is correct
17 Correct 3034 ms 66888 KB Output is correct