oj.uz

답안 #897190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897190 2024-01-02T17:10:56 Z bLIC Regions (IOI09_regions) C++17
17 / 100
 3690 ms 32396 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 uniq(v) v.erase(unique(all(v)), v.end())
#define ft first
#define sd second
#define pb push_back
#define eb emplace_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> bool chmin(T& a, T b){return (a>b?a=b,1:0);}
template<class T> bool chmax(T& a, T b){return (a<b?a=b,1:0);}
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
// Read the statement carefully


const int N = 2e5+1, R = 25000;
const int B = 450;

vvi adj, emp, tour;
vi reg, idofreg, currcnt, st, en;
vvl cntans;
vector<int> anc;
int timer;

void dfs(int node){
    st[node] = timer++;
    tour[reg[node]].push_back(st[node]);
    int id = idofreg[reg[node]];
    if (id && (currcnt[id]++)==0) anc.push_back(id);
    for (int x:adj[node]){
        for (int y:anc) cntans[y][reg[x]] += static_cast<ll>(currcnt[y]);
        dfs(x); 
    }
    if (id && (--currcnt[id])==0) anc.pop_back();
    en[node] = timer++;
}

void solve(){

    timer = 0;
    int n, r, q;cin>>n>>r>>q;
    adj.resize(n);
    emp.resize(r);
    tour.resize(r);
    reg.resize(n);
    idofreg.resize(r);
    currcnt.resize(r);
    st.resize(n);
    en.resize(n);
    anc.clear();
    {
        int x;cin>>x;
        x--;
        emp[x].push_back(0);
        reg[0] = x;
    }
    for (int i = 1;i<n;i++){
        int p, x;cin>>p>>x;
        x--;p--;
        reg[i] = x;
        emp[x].push_back(i);
        adj[p].push_back(i);
    }
    int rg = 0;
    for (int i = 0;i<r;i++){
        if (sz(emp[i])>=B) idofreg[i] = ++rg;
    }
    cntans.resize(rg+1, vl(r, 0ll));
    assert(rg<=B);
    dfs(0);
    while(q--){
        int r1, r2;cin>>r1>>r2;
        r1--;
        r2--;
        if (idofreg[r1]) cout<<cntans[idofreg[r1]][r2]<<endl;
        else {
            ll ans = 0;
            for (int e:emp[r1]){
                ans += lower_bound(all(tour[r2]), en[e]) - upper_bound(all(tour[r2]), st[e]);
            }
            cout<<ans<<endl;
        }
    }
}

int main() {

    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        cout<<'\n';
    }
}

Compilation message

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

Subtask #1
12.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 12 ms 344 KB Output is correct
8 Correct 20 ms 600 KB Output is correct
9 Correct 28 ms 1112 KB Output is correct
10 Correct 56 ms 1040 KB Output is correct
11 Correct 80 ms 1624 KB Output is correct
12 Correct 86 ms 2368 KB Output is correct
13 Runtime error 123 ms 1948 KB Execution killed with signal 13
14 Runtime error 221 ms 2632 KB Execution killed with signal 13
15 Runtime error 215 ms 6168 KB Execution killed with signal 13

Subtask #2
5.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1429 ms 7096 KB Execution killed with signal 13
2 Runtime error 1698 ms 5872 KB Execution killed with signal 13
3 Runtime error 2226 ms 9568 KB Execution killed with signal 13
4 Runtime error 183 ms 2956 KB Execution killed with signal 13
5 Runtime error 242 ms 5304 KB Execution killed with signal 13
6 Correct 344 ms 8396 KB Output is correct
7 Runtime error 1145 ms 7848 KB Execution killed with signal 13
8 Runtime error 684 ms 21272 KB Execution killed with signal 13
9 Runtime error 1831 ms 14648 KB Execution killed with signal 13
10 Runtime error 2872 ms 32396 KB Execution killed with signal 13
11 Runtime error 3690 ms 16052 KB Execution killed with signal 13
12 Runtime error 1064 ms 16872 KB Execution killed with signal 13
13 Runtime error 1397 ms 17312 KB Execution killed with signal 13
14 Runtime error 1570 ms 20784 KB Execution killed with signal 13
15 Runtime error 2489 ms 23292 KB Execution killed with signal 13
16 Runtime error 2240 ms 30472 KB Execution killed with signal 13
17 Runtime error 2225 ms 31868 KB Execution killed with signal 13