oj.uz

Submission #241289

# Submission time Handle Problem Language Result Execution time Memory
241289 2020-06-23T17:44:23 Z Mercenary Regions (IOI09_regions) C++14
0 / 100
 9 ms 6016 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) << '\n';
	}

	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:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
2 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
3 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
4 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
5 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
6 Incorrect 7 ms 5888 KB Unexpected end of file - int32 expected
7 Incorrect 8 ms 5888 KB Unexpected end of file - int32 expected
8 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
9 Incorrect 8 ms 5888 KB Unexpected end of file - int32 expected
10 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
11 Incorrect 8 ms 5676 KB Unexpected end of file - int32 expected
12 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
13 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
14 Incorrect 8 ms 5792 KB Unexpected end of file - int32 expected
15 Incorrect 9 ms 5760 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
2 Incorrect 8 ms 5888 KB Unexpected end of file - int32 expected
3 Incorrect 8 ms 5888 KB Unexpected end of file - int32 expected
4 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
5 Incorrect 8 ms 5888 KB Unexpected end of file - int32 expected
6 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
7 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
8 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
9 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
10 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
11 Incorrect 9 ms 6016 KB Unexpected end of file - int32 expected
12 Incorrect 8 ms 5888 KB Unexpected end of file - int32 expected
13 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected
14 Incorrect 8 ms 5936 KB Unexpected end of file - int32 expected
15 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
16 Incorrect 7 ms 5760 KB Unexpected end of file - int32 expected
17 Incorrect 8 ms 5760 KB Unexpected end of file - int32 expected