oj.uz

답안 #897193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897193 2024-01-02T17:12:38 Z bLIC Regions (IOI09_regions) C++17
11 / 100
 3500 ms 31008 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]);
    if (idofreg[reg[node]] && (currcnt[idofreg[reg[node]]]++)==0) anc.push_back(idofreg[reg[node]]);
    for (int x:adj[node]){
        for (int y:anc) cntans[y][reg[x]] += static_cast<ll>(currcnt[y]);
        dfs(x); 
    }
    if (idofreg[reg[node]] && (--currcnt[idofreg[reg[node]]])==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:169:14: warning: unused variable 'i' [-Wunused-variable]
  169 |     int t=1, i = 1;
      |              ^

Subtask #1
11.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 11 ms 344 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 21 ms 600 KB Output is correct
9 Correct 23 ms 856 KB Output is correct
10 Runtime error 59 ms 1020 KB Execution killed with signal 13
11 Runtime error 80 ms 1624 KB Execution killed with signal 13
12 Runtime error 95 ms 2100 KB Execution killed with signal 13
13 Correct 132 ms 1960 KB Output is correct
14 Correct 208 ms 2552 KB Output is correct
15 Runtime error 215 ms 5544 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1379 ms 6872 KB Execution killed with signal 13
2 Runtime error 1636 ms 5844 KB Execution killed with signal 13
3 Runtime error 2183 ms 9020 KB Execution killed with signal 13
4 Runtime error 181 ms 3168 KB Execution killed with signal 13
5 Runtime error 237 ms 4912 KB Execution killed with signal 13
6 Runtime error 329 ms 8296 KB Execution killed with signal 13
7 Runtime error 1154 ms 7776 KB Execution killed with signal 13
8 Runtime error 819 ms 20204 KB Execution killed with signal 13
9 Runtime error 1727 ms 14356 KB Execution killed with signal 13
10 Runtime error 2764 ms 31008 KB Execution killed with signal 13
11 Runtime error 3500 ms 16004 KB Execution killed with signal 13
12 Runtime error 1069 ms 16828 KB Execution killed with signal 13
13 Runtime error 1455 ms 17052 KB Execution killed with signal 13
14 Runtime error 1632 ms 20640 KB Execution killed with signal 13
15 Runtime error 2568 ms 22204 KB Execution killed with signal 13
16 Runtime error 2465 ms 27500 KB Execution killed with signal 13
17 Runtime error 2192 ms 29280 KB Execution killed with signal 13