oj.uz

답안 #718193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
718193 2023-04-03T15:32:28 Z bLIC Regions (IOI09_regions) C++17
1 / 100
 5247 ms 82768 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;
vvi adj(maxN);
vi regof(maxN);
vvi timing(maxK);
vi st(maxN), en(maxN);
vvi reg(maxK);
vector<bool> heavy(maxK);
unordered_map<int, int> cont;
unordered_map<int, int> ansforheavy[maxK];
int tim, hvy;


void dfs(int node){
    st[node] = tim++;
    if (heavy[regof[node]]){
        cont[regof[node]]++;
    }
    timing[regof[node]].push_back(st[node]);
    for (int x:adj[node]){
        for (auto y:cont){
            ansforheavy[regof[x]][y.ft] += y.sd;
        }
        dfs(x);
    }
    en[node] = tim;
    if (heavy[regof[node]]){
        cont[regof[node]]--;
    }
}

ll query(int r1, int r2){
    if (heavy[r1]) return ansforheavy[regof[r2]][regof[r1]];
    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);
        if (sz(reg[regof[i]])>B+1) reg[regof[i]].pop_back();
        adj[p].push_back(i);
    }
    
    for (int i = 1;i<=r;i++){
        if (sz(reg[i])>B){
            heavy[i] = true;
        }
    }
    dfs(1);

    while(q--){
        int r1, r2;
        cin>>r1>>r2;
        cout<<query(r1, r2)<<endl;
    }
}

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:176:14: warning: unused variable 'i' [-Wunused-variable]
  176 |     int t=1, i = 1;
      |              ^

Subtask #1
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 9808 KB Execution killed with signal 13
2 Runtime error 5 ms 9804 KB Execution killed with signal 13
3 Runtime error 9 ms 9888 KB Execution killed with signal 13
4 Runtime error 9 ms 9924 KB Execution killed with signal 13
5 Runtime error 13 ms 9936 KB Execution killed with signal 13
6 Runtime error 28 ms 9964 KB Execution killed with signal 13
7 Runtime error 28 ms 9936 KB Execution killed with signal 13
8 Runtime error 32 ms 9936 KB Execution killed with signal 13
9 Runtime error 62 ms 10704 KB Execution killed with signal 13
10 Correct 53 ms 10360 KB Output is correct
11 Runtime error 134 ms 10576 KB Execution killed with signal 13
12 Runtime error 147 ms 11284 KB Execution killed with signal 13
13 Runtime error 198 ms 10648 KB Execution killed with signal 13
14 Runtime error 313 ms 11180 KB Execution killed with signal 13
15 Runtime error 231 ms 16092 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1937 ms 14592 KB Execution killed with signal 13
2 Runtime error 2164 ms 12532 KB Execution killed with signal 13
3 Runtime error 2770 ms 17444 KB Execution killed with signal 13
4 Runtime error 300 ms 11352 KB Execution killed with signal 13
5 Runtime error 412 ms 14340 KB Execution killed with signal 13
6 Runtime error 747 ms 30240 KB Execution killed with signal 13
7 Runtime error 1811 ms 20672 KB Execution killed with signal 13
8 Runtime error 1267 ms 63656 KB Execution killed with signal 13
9 Runtime error 2545 ms 18764 KB Execution killed with signal 13
10 Runtime error 4267 ms 82768 KB Execution killed with signal 13
11 Runtime error 5247 ms 17044 KB Execution killed with signal 13
12 Runtime error 1759 ms 21008 KB Execution killed with signal 13
13 Runtime error 2297 ms 22096 KB Execution killed with signal 13
14 Runtime error 2689 ms 34552 KB Execution killed with signal 13
15 Runtime error 3641 ms 31396 KB Execution killed with signal 13
16 Runtime error 3626 ms 44344 KB Execution killed with signal 13
17 Runtime error 3749 ms 53916 KB Execution killed with signal 13