oj.uz

Submission #490587

# Submission time Handle Problem Language Result Execution time Memory
490587 2021-11-28T07:21:56 Z CyberSleeper Regions (IOI09_regions) C++14
100 / 100
 3917 ms 50720 KB 
#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ld          long double
#define pii         pair<int, int>
#define pll         pair<ll, ll>
#define ar3         array<int, 3>
#define nl          endl
#define tb          '\t'
#define sp          ' '
using namespace std;

const int MX=200005, MOD=1e9+7, BLOCK=500, INF=1e9+7, INFF=1e18+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

int N, R, Q, op[MX], ed[MX], reg[MX];
vector<int> adj[MX], euler;
vector<pii> rakyat[25005];

void DFS(int p, int x){
    op[x]=euler.size();
    euler.pb(reg[x]);
    for(auto i:adj[x]){
        DFS(x, i);
    }
    ed[x]=euler.size()-1;
}

int main(){
    //fastio;
    cin >> N >> R >> Q >> reg[1];
    for(int i=2, P; i<=N; i++){
        cin >> P >> reg[i];
        adj[P].pb(i);
    }
    DFS(0, 1);
    for(int i=1; i<=N; i++){
        int tmp=reg[i];
        rakyat[tmp].pb({op[i], ed[i]});
    }
    for(int i=0; i<=R; i++)
        sort(rakyat[i].begin(), rakyat[i].end());
    map<pii, int> prec;
    for(int i=1; i<=R; i++){
        if(rakyat[i].size()>BLOCK){
            int cnt=0, idx=0;
            vector<int> sweep(N+1, 0);
            for(auto j:rakyat[i]){
                sweep[j.fi]++;
                sweep[j.se+1]--;
            }
            for(int j=0; j<N; j++){
                cnt+=sweep[j];
                prec[{i, euler[j]}]+=cnt;
            }
        }
    }
    for(int u, v; Q--;){
        cin >> u >> v;
        if(rakyat[u].size()>BLOCK)
            cout << prec[{u, v}] << nl;
        else{
            int ans=0;
            for(auto i:rakyat[u]){
                int add=upper_bound(rakyat[v].begin(), rakyat[v].end(), mp(i.se, INF))-rakyat[v].begin();
                int dic=lower_bound(rakyat[v].begin(), rakyat[v].end(), mp(i.fi, -INF))-rakyat[v].begin();
                ans+=add-dic;
            }
            cout << ans << nl;
        }
    }
}

Compilation message

regions.cpp:18:64: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int MX=200005, MOD=1e9+7, BLOCK=500, INF=1e9+7, INFF=1e18+7;
      |                                                            ~~~~^~
regions.cpp: In function 'int main()':
regions.cpp:51:24: warning: unused variable 'idx' [-Wunused-variable]
   51 |             int cnt=0, idx=0;
      |                        ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5576 KB Output is correct
2 Correct 4 ms 5576 KB Output is correct
3 Correct 4 ms 5576 KB Output is correct
4 Correct 6 ms 5480 KB Output is correct
5 Correct 11 ms 5576 KB Output is correct
6 Correct 18 ms 5576 KB Output is correct
7 Correct 15 ms 5576 KB Output is correct
8 Correct 34 ms 5704 KB Output is correct
9 Correct 54 ms 6088 KB Output is correct
10 Correct 96 ms 6088 KB Output is correct
11 Correct 68 ms 6600 KB Output is correct
12 Correct 138 ms 6984 KB Output is correct
13 Correct 169 ms 6612 KB Output is correct
14 Correct 281 ms 7368 KB Output is correct
15 Correct 270 ms 9928 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1908 ms 10804 KB Output is correct
2 Correct 2105 ms 9760 KB Output is correct
3 Correct 2663 ms 12744 KB Output is correct
4 Correct 327 ms 7240 KB Output is correct
5 Correct 365 ms 8896 KB Output is correct
6 Correct 1481 ms 8516 KB Output is correct
7 Correct 1598 ms 9576 KB Output is correct
8 Correct 1317 ms 14696 KB Output is correct
9 Correct 1994 ms 15312 KB Output is correct
10 Correct 3593 ms 19896 KB Output is correct
11 Correct 3917 ms 15064 KB Output is correct
12 Correct 1633 ms 19124 KB Output is correct
13 Correct 1677 ms 19272 KB Output is correct
14 Correct 2890 ms 40880 KB Output is correct
15 Correct 3213 ms 24396 KB Output is correct
16 Correct 2759 ms 29840 KB Output is correct
17 Correct 3371 ms 50720 KB Output is correct