oj.uz

답안 #718162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
718162 2023-04-03T13:37:52 Z bLIC Regions (IOI09_regions) C++17
0 / 100
 8000 ms 51940 KB 
/**
 *  Author: Anil Byar
**/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// template<class T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back

// Source: https://codeforces.com/blog/entry/68809
// { start
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// } end


typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 1e9+7;
const ll MOD9 = 998244353;
const ll INFLL = 1e18+5;
const int INF = 1e9;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}
ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;}
ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);}

template<class T>
istream& operator>>(istream&in, vector<T>&v){
    for (T& x:v) in>>x;
    return in;
}
template<class T>
ostream& operator<<(ostream&out, vector<T>&v){
    for (T& x:v) out<<x<<' ';
    cout<<'\n';
    return out;
}
// use ?: with brackets (?:)
// check for overflow
// think about dp


const int maxN = 2e5+5;
const int maxK = 25005;
const int B = 447;
int n, r, q;
vi adj[maxN];
int regof[maxN];
vi timing[maxK];
int st[maxN], en[maxN];
vi reg[maxK];
int indof[maxK];
int heavy[maxK];
vl cont;
vvl ansforheavy;
int tim, hvy;

inline int regcont(int r){return sz(reg[r]);}

void dfs(int node){
    st[node] = tim++;
    if (heavy[regof[node]]){
        cont[indof[regof[node]]]++;
        assert(indof[regof[node]]<hvy);
    }
    timing[regof[node]].push_back(st[node]);
    for (int x:adj[node]){
        for (int i = 0;i<hvy;i++){
            ansforheavy[i][regof[x]] += cont[i];
        }
        dfs(x);
    }
    en[node] = tim;
    if (heavy[regof[node]]){
        cont[indof[regof[node]]]--;
    }
}

ll query(int r1, int r2){
    if (heavy[r1]) return ansforheavy[indof[r1]][r2];
    else {
        ll ans = 0;
        for (int x:reg[r1]){
            ans += lower_bound(all(timing[r2]), en[x])-upper_bound(all(timing[r2]), st[x]);
        }
        return ans;
    }
}

void solve(){
    cin>>n>>r>>q;
    cin>>regof[1];
    reg[regof[1]].push_back(1);
    for (int i = 2;i<=n;i++){
        int p;
        cin>>p>>regof[i];
        reg[regof[i]].push_back(i);
        adj[p].push_back(i);
    }
    
    for (int i = 1;i<=r;i++){
        if (regcont(i)>B){
            heavy[i] = true;
            indof[i] = hvy++;
        }
    }
    ansforheavy.resize(hvy, vl(r+1));
    cont.resize(hvy, 0);
    dfs(1);
    for (int i = 1;i<=r;i++) {
        debug(i, timing[i]);
    }
    while(q--){
        int r1, r2;
        cin>>r1>>r2;
        debug(r1, timing[r1], r2, timing[r2]);
        cout<<query(r1, r2)<<endl;
        fflush(stdout);
    }
}

int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);


// #ifndef ONLINE_JUDGE
//     freopen("input.in", "r", stdin);
//     freopen("output.out", "w", stdout);
//     freopen("debug.dbg", "w", stderr);
//     int tt = clock();
// #endif

    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        cout<<'\n';
    }
// #ifndef ONLINE_JUDGE
//     cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
//     tt = clock();
// #endif
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:185:14: warning: unused variable 'i' [-Wunused-variable]
  185 |     int t=1, i = 1;
      |              ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 6096 KB Execution killed with signal 13
2 Runtime error 5 ms 6200 KB Execution killed with signal 13
3 Runtime error 13 ms 6096 KB Execution killed with signal 13
4 Runtime error 27 ms 6096 KB Execution killed with signal 13
5 Runtime error 91 ms 6236 KB Execution killed with signal 13
6 Runtime error 132 ms 6392 KB Execution killed with signal 13
7 Runtime error 273 ms 6680 KB Execution killed with signal 13
8 Runtime error 338 ms 6732 KB Execution killed with signal 13
9 Runtime error 688 ms 7824 KB Execution killed with signal 13
10 Runtime error 1313 ms 9080 KB Execution killed with signal 13
11 Runtime error 3584 ms 13460 KB Execution killed with signal 13
12 Runtime error 3477 ms 14196 KB Execution killed with signal 13
13 Runtime error 6514 ms 19120 KB Execution killed with signal 13
14 Execution timed out 8028 ms 22244 KB Time limit exceeded
15 Execution timed out 8006 ms 24488 KB Time limit exceeded

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8071 ms 26440 KB Time limit exceeded
2 Execution timed out 8026 ms 23952 KB Time limit exceeded
3 Execution timed out 8080 ms 28712 KB Time limit exceeded
4 Execution timed out 8022 ms 23452 KB Time limit exceeded
5 Execution timed out 8076 ms 25344 KB Time limit exceeded
6 Execution timed out 8090 ms 28624 KB Time limit exceeded
7 Execution timed out 8005 ms 27584 KB Time limit exceeded
8 Execution timed out 8070 ms 39588 KB Time limit exceeded
9 Execution timed out 8026 ms 33064 KB Time limit exceeded
10 Execution timed out 8074 ms 49052 KB Time limit exceeded
11 Execution timed out 8032 ms 31872 KB Time limit exceeded
12 Execution timed out 8023 ms 32828 KB Time limit exceeded
13 Execution timed out 8016 ms 32836 KB Time limit exceeded
14 Execution timed out 8099 ms 37904 KB Time limit exceeded
15 Execution timed out 8053 ms 42484 KB Time limit exceeded
16 Execution timed out 8052 ms 49676 KB Time limit exceeded
17 Execution timed out 8061 ms 51940 KB Time limit exceeded