oj.uz

Submission #155702

# Submission time Handle Problem Language Result Execution time Memory
155702 2019-09-30T01:08:03 Z Mercenary Regions (IOI09_regions) C++14
0 / 100
 67 ms 12792 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] << endl;
}

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 7 ms 5624 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 5620 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 5624 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 5624 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 5652 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 5624 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 5752 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 5880 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 6136 KB Time limit exceeded (wall clock)
12 Execution timed out 13 ms 6344 KB Time limit exceeded (wall clock)
13 Execution timed out 13 ms 6008 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 6520 KB Time limit exceeded (wall clock)
15 Execution timed out 17 ms 6952 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 26 ms 8108 KB Time limit exceeded (wall clock)
2 Execution timed out 27 ms 7412 KB Time limit exceeded (wall clock)
3 Execution timed out 29 ms 8696 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 6504 KB Time limit exceeded (wall clock)
5 Execution timed out 17 ms 6904 KB Time limit exceeded (wall clock)
6 Execution timed out 21 ms 7288 KB Time limit exceeded (wall clock)
7 Execution timed out 25 ms 7672 KB Time limit exceeded (wall clock)
8 Execution timed out 33 ms 9224 KB Time limit exceeded (wall clock)
9 Execution timed out 48 ms 10616 KB Time limit exceeded (wall clock)
10 Execution timed out 55 ms 11768 KB Time limit exceeded (wall clock)
11 Execution timed out 65 ms 10104 KB Time limit exceeded (wall clock)
12 Execution timed out 65 ms 12296 KB Time limit exceeded (wall clock)
13 Execution timed out 59 ms 11768 KB Time limit exceeded (wall clock)
14 Execution timed out 64 ms 11640 KB Time limit exceeded (wall clock)
15 Execution timed out 67 ms 12664 KB Time limit exceeded (wall clock)
16 Execution timed out 65 ms 12792 KB Time limit exceeded (wall clock)
17 Execution timed out 65 ms 12792 KB Time limit exceeded (wall clock)