oj.uz

Submission #241292

# Submission time Handle Problem Language Result Execution time Memory
241292 2020-06-23T17:46:22 Z Mercenary Regions (IOI09_regions) C++14
100 / 100
 5311 ms 90924 KB 
#define LOCAL
#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) << endl;
	}
 
	return 0;
}
 
#endif // LOCAL

Compilation message

regions.cpp: In function 'void init(int, int, int, int*, int*)':
regions.cpp:88:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 0;
         ^~~
regions.cpp: In function 'int main()':
regions.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &R, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &H[0]);
  ~~~~~^~~~~~~~~~~~~
regions.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &S[i], &H[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &r1, &r2);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5760 KB Output is correct
2 Correct 8 ms 5760 KB Output is correct
3 Correct 10 ms 5760 KB Output is correct
4 Correct 12 ms 5760 KB Output is correct
5 Correct 15 ms 5888 KB Output is correct
6 Correct 30 ms 5888 KB Output is correct
7 Correct 46 ms 5888 KB Output is correct
8 Correct 40 ms 6016 KB Output is correct
9 Correct 78 ms 6656 KB Output is correct
10 Correct 116 ms 6528 KB Output is correct
11 Correct 161 ms 6912 KB Output is correct
12 Correct 146 ms 7680 KB Output is correct
13 Correct 189 ms 7936 KB Output is correct
14 Correct 343 ms 8192 KB Output is correct
15 Correct 304 ms 13048 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1650 ms 13688 KB Output is correct
2 Correct 1674 ms 15096 KB Output is correct
3 Correct 2968 ms 16632 KB Output is correct
4 Correct 297 ms 8448 KB Output is correct
5 Correct 417 ms 11264 KB Output is correct
6 Correct 1650 ms 10488 KB Output is correct
7 Correct 2133 ms 11896 KB Output is correct
8 Correct 1538 ms 20600 KB Output is correct
9 Correct 2721 ms 19452 KB Output is correct
10 Correct 5194 ms 28280 KB Output is correct
11 Correct 5311 ms 24056 KB Output is correct
12 Correct 1985 ms 51576 KB Output is correct
13 Correct 2521 ms 53912 KB Output is correct
14 Correct 2444 ms 64056 KB Output is correct
15 Correct 4170 ms 77944 KB Output is correct
16 Correct 4054 ms 90924 KB Output is correct
17 Correct 3865 ms 79436 KB Output is correct