Submission #241288

# Submission time Handle Problem Language Result Execution time Memory
241288 2020-06-23T17:42:56 Z Mercenary Regions (IOI09_regions) C++14
Compilation error
0 ms 0 KB
#ifndef LOCAL
#include "regions.h"
#endif // LOCAL

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 5;
const int maxr = 25005;
const int MAGIC = 505;

int n , r , q;
int col[maxn];
vector<int> adj[maxn];
int in[maxn] , out[maxn] , rv[maxn];
int PRECAL_ANS[maxr][MAGIC];
int PRECAL_ANS1[MAGIC][maxr];

vector<int> gr[maxr];
int cnt1[maxr];
int BIG = 0;
int id[maxr];

map<int,int> *mmap[maxn];
int sub[maxn];
void dfs1(int u){
    sub[u] = 1;
    for(auto &c : adj[u]){
        dfs1(c);
        sub[u] += sub[c];
        if(sub[c] > sub[adj[u][0]])swap(c,adj[u][0]);
    }
}
void dfs(int u){
    static int nTime = 0;
    in[u] = ++nTime;
    rv[nTime] = u;
    if(id[col[u]] != -1)cnt1[id[col[u]]]++;
    for(int j = 0 ; j < BIG ; ++j){
        PRECAL_ANS1[j][col[u]] += cnt1[j];
        assert(PRECAL_ANS1[j][col[u]] <= 1e9);
    }
    for(auto c : adj[u]){
        dfs(c);
    }
    if(adj[u].size() == 0)mmap[u] = new map<int,int>();
    else mmap[u] = mmap[adj[u][0]];
    for(auto c : adj[u]){
        if(c != adj[u][0]){
            for(auto d : (*mmap[c])){
                (*mmap[u])[d.first] += d.second;
            }
        }
    }
    if(id[col[u]] != -1){
        cnt1[id[col[u]]]--;
        (*mmap[u])[id[col[u]]]++;
    }
    for(auto c : (*mmap[u])){
        PRECAL_ANS[col[u]][c.first] += c.second;
//        assert(PRECAL_ANS[col[u]][c.first] <= 1e9);
    }
    out[u] = nTime;
}

void init(int N, int R, int Q, int S[], int H[]) {
    n = N;r = R;
    for(int i = 0 ; i < n ; ++i){
        col[i + 1] = H[i];
        if(i > 0)adj[S[i]].pb(i + 1);
        gr[col[i + 1]].pb(i + 1);
    }
    memset(id,-1,sizeof id);
    int cnt = 0;
    for(int i = 1 ; i <= r ; ++i){
        if(gr[i].size() >= MAGIC){
            id[i] = BIG++;
        }
    }
    dfs1(1);
    dfs(1);
    for(int i = 1 ; i <= r ; ++i){
        for(auto & c : gr[i])c = in[c];
        sort(gr[i].begin(),gr[i].end());
    }
    return;
}

int query(int r1, int r2) {
    if(id[r2] != -1)return PRECAL_ANS[r1][id[r2]];
    if(id[r1] != -1)return PRECAL_ANS1[id[r1]][r2];
    int res = 0;
    for(auto & c : gr[r1]){
        int & tmp = rv[c];
        res += upper_bound(gr[r2].begin(),gr[r2].end(),out[tmp])
        -lower_bound(gr[r2].begin(),gr[r2].end(),in[tmp]);
    }
//    assert(res >= 0);
	return res;
}

#ifdef LOCAL
#include <vector>
#include <cstdio>
using namespace std;

int N,Q,R;
int H[200005];
int S[200005];
int ans[200005];

int main () {
    freopen("A.INP","r",stdin);
    freopen("A.OUT","w",stdout);
	scanf("%d%d%d", &N, &R, &Q);
	scanf("%d", &H[0]);
	S[0] = -1;
	for (int i = 1; i < N; i++) {
		scanf("%d%d", &S[i], &H[i]);
	}
	init(N,R,Q,S,H);
	for (int i = 0; i < Q; i++) {
		int r1,r2;
		scanf("%d%d", &r1, &r2);
		cout << query(r1,r2) << '\n';
	}

	return 0;
}

#endif // LOCAL

Compilation message

regions.cpp:2:10: fatal error: regions.h: No such file or directory
 #include "regions.h"
          ^~~~~~~~~~~
compilation terminated.