Submission #1126132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126132		wibulord	Regions (IOI09_regions)	C++20	0 / 100	49 ms	26336 KiB

regions

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define pb emplace_back
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define sz(s) (int)((s).size())
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
using namespace std;

template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}

const int MOD = (int)1e9 + 7;
const int mod = 998244353; 
const int N = 2e5 + 1, M = 18, Max = 100;

/*
     /\_/\
    (= ._.)
    / >?  \>$
*/
struct Query{
    int r1, r2, idx;
    void init(int i){
        cin >> r1 >> r2;
        idx = i;
    }

    bool operator < (const Query &p) const{
        return r1 == p.r1 ? r2 < p.r2 : r1 < p.r1;
    }
}Q[N];

int n, r, q, timer; 
long long ans[N];
int h[N], cnt[N], num[N], tail[N], src[N], region[N];
vector<int> In[N], Out[N], adj[N];
vector<Query> Q1;
vector<pair<int, int>> Q2[N]; 

void dfs(int u){ 
    num[u] = ++timer;
    for(pair<int, int> it : Q2[h[u]]){
        int r1 = it.fi, idx = it.se;
        ans[idx] += cnt[r1];
    }
    In[h[u]].push_back(num[u]);
    cnt[h[u]]++;
    for(int v : adj[u]) dfs(v);
    cnt[h[u]]--;
    tail[u] = timer;
    Out[h[u]].push_back(tail[u]);
}

void sol(void){
    cin >> n >> r >> q; 
    FOR(i, 1, n){
        if(i > 1){
            int p; cin >> p;
            adj[p].pb(i);
        } 
        cin >> h[i];
        region[h[i]]++;
    } 
    FOR(i, 1, q) Q[i].init(i);
    sort(Q+1,Q+q+1);
    FOR(i, 1, q){
        int r1 = Q[i].r1, r2 = Q[i].r2, idx = Q[i].idx;
        if(r1 == Q[i-1].r1 && r2 == Q[i-1].r2){
            src[idx] = src[Q[i-1].idx];
            continue;
        }
        src[idx] = idx;
        if(region[r1] >= Max) Q2[r2].push_back(make_pair(r1, idx));
        else Q1.push_back(Q[i]);
    }
    dfs(1);  
    for(auto [r1, r2, idx] : Q1){
        for(int x : In[r1]) ans[idx] -= lower_bound(all(In[r2]), x) - In[r2].begin();
        for(int x : Out[r1]) ans[idx] += upper_bound(all(In[r2]), x) - In[r2].begin();
    }
    FOR(i, 1, q) cout << ans[src[i]] << ' ';
}

signed main(void){
    #define TASK "nhap"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
//    cin >> t;
    while(t--) sol();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85