oj.uz

답안 #799771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799771 2023-08-01T01:20:07 Z Haidara Regions (IOI09_regions) C++17
75 / 100
 3505 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: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 23788 KB Output is correct
2 Correct 11 ms 23760 KB Output is correct
3 Correct 12 ms 23760 KB Output is correct
4 Correct 14 ms 23724 KB Output is correct
5 Correct 17 ms 23760 KB Output is correct
6 Correct 28 ms 23900 KB Output is correct
7 Correct 35 ms 23804 KB Output is correct
8 Correct 34 ms 23888 KB Output is correct
9 Correct 46 ms 24296 KB Output is correct
10 Correct 85 ms 24272 KB Output is correct
11 Correct 95 ms 24656 KB Output is correct
12 Correct 116 ms 25084 KB Output is correct
13 Correct 172 ms 25168 KB Output is correct
14 Correct 195 ms 25548 KB Output is correct
15 Correct 265 ms 29156 KB Output is correct

Subtask #2
60.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1334 ms 29808 KB Output is correct
2 Correct 1395 ms 29964 KB Output is correct
3 Correct 2048 ms 31344 KB Output is correct
4 Correct 255 ms 25648 KB Output is correct
5 Correct 294 ms 27088 KB Output is correct
6 Correct 762 ms 44436 KB Output is correct
7 Correct 1397 ms 51836 KB Output is correct
8 Correct 1619 ms 81868 KB Output is correct
9 Correct 3266 ms 97036 KB Output is correct
10 Runtime error 1616 ms 131072 KB Execution killed with signal 9
11 Runtime error 2551 ms 131072 KB Execution killed with signal 9
12 Runtime error 3505 ms 131072 KB Execution killed with signal 9
13 Runtime error 3024 ms 131072 KB Execution killed with signal 9
14 Correct 2348 ms 53532 KB Output is correct
15 Correct 2568 ms 43396 KB Output is correct
16 Runtime error 1594 ms 131072 KB Execution killed with signal 9
17 Correct 3178 ms 66828 KB Output is correct