oj.uz

Submission #155701

# Submission time Handle Problem Language Result Execution time Memory
155701 2019-09-30T01:07:16 Z Mercenary Regions (IOI09_regions) C++14
0 / 100
 68 ms 12864 KB 
#include<bits/stdc++.h>
#define taskname "UNDRA"
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 2e5 + 5;
const int maxr = 25005;
const int sqr = 450 + 5;

int bigid[maxr];
int col[maxr];
int n , r , q;
vector<int> adj[maxn];
int big[sqr];
int nBig = 0;
vector<ii> querysmall[maxr];
int precal[sqr][maxr];
int c[maxn];
int cnt[maxr];
int res[maxn];

void DFS(int u){
    if(bigid[c[u]]){
        for(int i = 1 ; i <= r ; ++i){
            precal[bigid[c[u]]][i] += cnt[i];
        }
    }else{
        for(const ii& v : querysmall[c[u]]){
            res[v.second] += cnt[v.first];
        }
    }
    cnt[c[u]]++;
    for(auto & v : adj[u]){
        DFS(v);
    }
    cnt[c[u]]--;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    cin >> n >> r >> q;
    for(int p , i = 1 ; i <= n ; ++i){
        if(i > 1){
            cin >> p >> c[i];
            adj[p].pb(i);
        }
        else cin >> c[i];
        col[c[i]]++;
    }
    for(int i = 1 ; i <= r ; ++i){
        if(col[i] >= sqr){
            bigid[i] = ++nBig;
            big[nBig] = i;
        }
    }
    for(int r1 , r2,  i = 1 ; i <= q ; ++i){
        cin >> r1 >> r2;
        querysmall[r2].pb(mp(r1 , i));
    }
    DFS(1);
    for(int i = 1 ; i <= nBig ; ++i){
        for(auto & v : querysmall[big[i]]){
            res[v.second] = precal[i][v.first];
        }
    }
    for(int i = 1 ; i <= q ; ++i)cout << res[i] << '\n';
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP","r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT","w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 5624 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 5624 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 5624 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 5624 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 5628 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 5624 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 5628 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 5624 KB Time limit exceeded (wall clock)
9 Execution timed out 8 ms 5880 KB Time limit exceeded (wall clock)
10 Execution timed out 9 ms 5888 KB Time limit exceeded (wall clock)
11 Execution timed out 11 ms 6056 KB Time limit exceeded (wall clock)
12 Execution timed out 11 ms 6312 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 6008 KB Time limit exceeded (wall clock)
14 Execution timed out 15 ms 6440 KB Time limit exceeded (wall clock)
15 Execution timed out 17 ms 7032 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 26 ms 8056 KB Time limit exceeded (wall clock)
2 Execution timed out 29 ms 7444 KB Time limit exceeded (wall clock)
3 Execution timed out 32 ms 8724 KB Time limit exceeded (wall clock)
4 Execution timed out 15 ms 6392 KB Time limit exceeded (wall clock)
5 Execution timed out 17 ms 6924 KB Time limit exceeded (wall clock)
6 Execution timed out 20 ms 7160 KB Time limit exceeded (wall clock)
7 Execution timed out 25 ms 7800 KB Time limit exceeded (wall clock)
8 Execution timed out 33 ms 9208 KB Time limit exceeded (wall clock)
9 Execution timed out 49 ms 10488 KB Time limit exceeded (wall clock)
10 Execution timed out 55 ms 11768 KB Time limit exceeded (wall clock)
11 Execution timed out 66 ms 9976 KB Time limit exceeded (wall clock)
12 Execution timed out 60 ms 12284 KB Time limit exceeded (wall clock)
13 Execution timed out 60 ms 11724 KB Time limit exceeded (wall clock)
14 Execution timed out 64 ms 11688 KB Time limit exceeded (wall clock)
15 Execution timed out 65 ms 12792 KB Time limit exceeded (wall clock)
16 Execution timed out 66 ms 12720 KB Time limit exceeded (wall clock)
17 Execution timed out 68 ms 12864 KB Time limit exceeded (wall clock)