oj.uz

Submission #490585

# Submission time Handle Problem Language Result Execution time Memory
490585 2021-11-28T05:52:17 Z CyberSleeper Regions (IOI09_regions) C++14
30 / 100
 3296 ms 131076 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=0, 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[v])
                ans+=upper_bound(rakyat[u].begin(), rakyat[u].end(), mp(i.fi, -INF))-lower_bound(rakyat[u].begin(), rakyat[u].end(), mp(i.se, INF));
            cout << ans << nl;
        }
    }
}

Compilation message

regions.cpp:18:62: 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=0, 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 3 ms 5576 KB Output is correct
2 Correct 3 ms 5576 KB Output is correct
3 Correct 4 ms 5576 KB Output is correct
4 Correct 8 ms 5576 KB Output is correct
5 Correct 10 ms 5704 KB Output is correct
6 Correct 44 ms 9300 KB Output is correct
7 Correct 41 ms 7004 KB Output is correct
8 Correct 72 ms 8208 KB Output is correct
9 Correct 154 ms 11688 KB Output is correct
10 Correct 453 ms 17300 KB Output is correct
11 Correct 404 ms 10964 KB Output is correct
12 Correct 900 ms 19704 KB Output is correct
13 Correct 819 ms 13972 KB Output is correct
14 Correct 582 ms 9892 KB Output is correct
15 Correct 1079 ms 13532 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1645 ms 13320 KB Output is correct
2 Correct 1938 ms 12712 KB Output is correct
3 Correct 2803 ms 16896 KB Output is correct
4 Runtime error 2480 ms 131076 KB Execution killed with signal 9
5 Runtime error 2903 ms 131076 KB Execution killed with signal 9
6 Runtime error 2017 ms 131076 KB Execution killed with signal 9
7 Runtime error 1951 ms 131076 KB Execution killed with signal 9
8 Runtime error 2243 ms 131076 KB Execution killed with signal 9
9 Runtime error 2939 ms 131076 KB Execution killed with signal 9
10 Runtime error 1908 ms 131076 KB Execution killed with signal 9
11 Runtime error 2504 ms 131076 KB Execution killed with signal 9
12 Runtime error 3296 ms 131076 KB Execution killed with signal 9
13 Runtime error 3014 ms 131076 KB Execution killed with signal 9
14 Runtime error 2981 ms 131076 KB Execution killed with signal 9
15 Runtime error 2109 ms 131076 KB Execution killed with signal 9
16 Runtime error 2012 ms 131076 KB Execution killed with signal 9
17 Runtime error 2641 ms 131076 KB Execution killed with signal 9