Submission #355542

#	Time	Username	Problem	Language	Result	Execution time	Memory
355542		parsabahrami	Regions (IOI09_regions)	C++17	Compilation error	0 ms	0 KiB

regions

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10, SQ = 450;
map<int, int> Cup[N], Cdown[N], C1[N], C2[N]; vector<pii> vec[N];
int A[N], S[N], St[N], Ft[N], n, R, q, tim; vector<int> adj[N];

void preDFS(int v) {
    St[v] = tim++;
    for (int u : adj[v]) {
        preDFS(u);
    }
    Ft[v] = tim;
}

void DFS(int v, int p = -1) {
    if (~p) {
        Cup[v] = Cup[p];
        if (S[A[p]] > SQ) Cup[v][A[p]]++;
    }
    for (int u : adj[v]) {
        DFS(u, v);
        unordered_map<int, int> tmp = Cdown[u];
        if (SZ(tmp) > SZ(Cdown[v])) Cdown[v].swap(tmp);
        for (pii x : tmp) Cdown[v][x.F] += x.S;
        if (S[A[u]] > SQ) Cdown[v][A[u]]++;
    }
}

int main() {
    scanf("%d%d%d%d", &n, &R, &q, &A[1]);
    for (int i = 2; i <= n; i++) {
        int p; scanf("%d%d", &p, &A[i]);
        adj[p].push_back(i);
    }
    preDFS(1);
    for (int i = 1; i <= n; i++) vec[A[i]].push_back({St[i], i});
    for (int i = 1; i <= R; i++) sort(vec[i].begin(), vec[i].end()), S[i] = SZ(vec[i]);
    DFS(1);
    for (int i = 1; i <= n; i++) {
        for (pii x : Cup[i]) C1[A[i]][x.F] += x.S;
        for (pii x : Cdown[i]) C2[A[i]][x.F] += x.S;
    }
    for (; q; q--) {
        int r1, r2; scanf("%d%d", &r1, &r2);
        if (S[r1] > SQ) printf("%d\n", C1[r2][r1]);
        else if (S[r2] > SQ) printf("%d\n", C2[r1][r2]);
        else {
            int l = 0, r = 0, ret = 0;
            for (pii x : vec[r1]) {
                int v = x.S;
                while (r < S[r2] && vec[r2][r].F < Ft[v]) r++;
                while (l < r && vec[r2][l].F < St[v]) l++;
                if (l == S[r2] || !r) continue;
                int u = vec[r2][l].S, w = vec[r2][r - 1].S;
                if (St[v] <= St[u] && Ft[u] <= Ft[v] && St[v] <= St[w] && Ft[w] <= Ft[v]) ret += r - l;
            }
            printf("%d\n", ret);
        }
        fflush(stdout);
    }
    return 0;   
}

Compilation message (stderr)

regions.cpp: In function 'void DFS(int, int)':
regions.cpp:32:46: error: conversion from 'std::map<int, int>' to non-scalar type 'std::unordered_map<int, int>' requested
   32 |         unordered_map<int, int> tmp = Cdown[u];
      |                                       ~~~~~~~^
regions.cpp:33:51: error: cannot convert 'std::unordered_map<int, int>' to 'std::map<int, int>&'
   33 |         if (SZ(tmp) > SZ(Cdown[v])) Cdown[v].swap(tmp);
      |                                                   ^~~
      |                                                   |
      |                                                   std::unordered_map<int, int>
In file included from /usr/include/c++/9/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from regions.cpp:2:
/usr/include/c++/9/bits/stl_map.h:1121:17: note:   initializing argument 1 of 'void std::map<_Key, _Tp, _Compare, _Alloc>::swap(std::map<_Key, _Tp, _Compare, _Alloc>&) [with _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
 1121 |       swap(map& __x)
      |            ~~~~~^~~
regions.cpp: In function 'int main()':
regions.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     scanf("%d%d%d%d", &n, &R, &q, &A[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:42:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         int p; scanf("%d%d", &p, &A[i]);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:54:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         int r1, r2; scanf("%d%d", &r1, &r2);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~