oj.uz

답안 #799769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799769 2023-08-01T01:14:01 Z Haidara Regions (IOI09_regions) C++17
75 / 100
 3542 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]>200)
        go(i);
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(cnt[r1]>200)
            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: 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 11 ms 23720 KB Output is correct
3 Correct 12 ms 23800 KB Output is correct
4 Correct 14 ms 23784 KB Output is correct
5 Correct 17 ms 23760 KB Output is correct
6 Correct 23 ms 23836 KB Output is correct
7 Correct 30 ms 23888 KB Output is correct
8 Correct 31 ms 24016 KB Output is correct
9 Correct 57 ms 24432 KB Output is correct
10 Correct 96 ms 24532 KB Output is correct
11 Correct 97 ms 25040 KB Output is correct
12 Correct 102 ms 25624 KB Output is correct
13 Correct 174 ms 25936 KB Output is correct
14 Correct 232 ms 26320 KB Output is correct
15 Correct 274 ms 30236 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1350 ms 31832 KB Output is correct
2 Correct 1351 ms 32712 KB Output is correct
3 Correct 2471 ms 33416 KB Output is correct
4 Correct 216 ms 26440 KB Output is correct
5 Correct 282 ms 27828 KB Output is correct
6 Correct 766 ms 51396 KB Output is correct
7 Correct 1482 ms 61256 KB Output is correct
8 Correct 1841 ms 99484 KB Output is correct
9 Correct 3542 ms 121652 KB Output is correct
10 Runtime error 1202 ms 131072 KB Execution killed with signal 9
11 Runtime error 1962 ms 131072 KB Execution killed with signal 9
12 Runtime error 2690 ms 131072 KB Execution killed with signal 9
13 Runtime error 2271 ms 131072 KB Execution killed with signal 9
14 Correct 2496 ms 64220 KB Output is correct
15 Correct 2597 ms 48096 KB Output is correct
16 Runtime error 1200 ms 131072 KB Execution killed with signal 9
17 Correct 2884 ms 77568 KB Output is correct