Submission #964896

#	Time	Username	Problem	Language	Result	Execution time	Memory
964896		codefox	Regions (IOI09_regions)	C++14	Compilation error	0 ms	0 KiB

regions

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#define pii pair<int, short>

int K = 200;
int N = 200000;
int R = 25000;

vector<int> graph[N];
short region[N];
int rind;

int start[N];
int ende[N];
int c =0 ;

vector<vector<int>> dpback;

int backsolutions[R][K];
int frontsolutions[K][R];

void dfsback(int i)
{
    start[i] = c++;
    for (int ele:graph[i])
    {
        dfsback(ele);
        for (int j = 0; j < K; j++)
        {
            dpback[i][j] += dpback[ele][j];
        }
    }
    for (int j = 0; j < K; j++)
    {
        backsolutions[region[i]][j] += dpback[i][j];
    }
    if (rind[region[i]]!= -1) dpback[i][rind[region[i]]]++;
    ende[i] = c;
}

void dfsfront(int i, vector<int> dpfront)
{
    for (int j = 0; j < K; j++)
    {
        frontsolutions[j][region[i]] += dpfront[j];
    }
    if (rind[region[i]]!=-1) dpfront[rind[region[i]]]++;
    for (int ele:graph[i])
    {
        dfsfront(ele, dpfront);
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, r, q;
    cin >> n >> r >> q;

    graph.assign(n, vector<int>());
    rind.assign(r, -1);

    for (int i = 0; i < R*K; i++)
    {
        backsolutions[0][i] = 0;
        frontsolutions[0][i] = 0;
    }

    vector<vector<int>> part(r);

    cin >> region[0];
    region[0]--;
    part[region[0]].push_back(0);
    for (int i = 1; i < n; i++)
    {
        int b;
        cin >> b;
        graph[b-1].push_back(i);
        cin >> region[i];
        region[i]--;
        part[region[i]].push_back(i);
    }

    vector<int> rsum(r, 0);
    int d =0;
    for (int i = 0; i < n; i++) rsum[region[i]]++;
    for (int i = 0; i < r; i++)
    {
        if (rsum[i]*K > N) 
        {
            rind[i] = d++;
        }
    }
    rsum.clear(0);

    dpback.assign(n, vector<int>(K, 0));

    dfsback(0);
    dpback.clear(0);
    dfsfront(0, vector<int>(K, 0));

    vector<pii> s;
    while (q--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (rind[a]!=-1) cout << frontsolutions[rind[a]][b] << endl;
        else if (rind[b]!=-1) cout << backsolutions[a][rind[b]] << endl;
        else
        {
            for (int ele:part[a]) 
            {
                s.push_back({start[ele], 2});
                s.push_back({ende[ele], 0});
            }
            for (int ele:part[b])
            {
                s.push_back({start[ele], 1});
            }
            sort(s.begin(), s.end());

            int open = 0;
            int sol = 0;
            for (pii ele:s)
            {
                if (ele.second == 0) open--;
                if (ele.second == 1) sol += open;
                if (ele.second == 2) open++;
            }
            cout << sol << endl;
            s.clear();
        }
    }

    return 0;
}

Compilation message (stderr)

regions.cpp:14:20: error: array bound is not an integer constant before ']' token
   14 | vector<int> graph[N];
      |                    ^
regions.cpp:15:15: error: array bound is not an integer constant before ']' token
   15 | short region[N];
      |               ^
regions.cpp:18:12: error: array bound is not an integer constant before ']' token
   18 | int start[N];
      |            ^
regions.cpp:19:11: error: array bound is not an integer constant before ']' token
   19 | int ende[N];
      |           ^
regions.cpp:24:20: error: array bound is not an integer constant before ']' token
   24 | int backsolutions[R][K];
      |                    ^
regions.cpp:24:23: error: array bound is not an integer constant before ']' token
   24 | int backsolutions[R][K];
      |                       ^
regions.cpp:25:21: error: array bound is not an integer constant before ']' token
   25 | int frontsolutions[K][R];
      |                     ^
regions.cpp:25:24: error: array bound is not an integer constant before ']' token
   25 | int frontsolutions[K][R];
      |                        ^
regions.cpp: In function 'void dfsback(int)':
regions.cpp:29:5: error: 'start' was not declared in this scope
   29 |     start[i] = c++;
      |     ^~~~~
regions.cpp:30:18: error: 'graph' was not declared in this scope; did you mean 'isgraph'?
   30 |     for (int ele:graph[i])
      |                  ^~~~~
      |                  isgraph
regions.cpp:40:9: error: 'backsolutions' was not declared in this scope
   40 |         backsolutions[region[i]][j] += dpback[i][j];
      |         ^~~~~~~~~~~~~
regions.cpp:40:23: error: 'region' was not declared in this scope
   40 |         backsolutions[region[i]][j] += dpback[i][j];
      |                       ^~~~~~
regions.cpp:42:14: error: 'region' was not declared in this scope
   42 |     if (rind[region[i]]!= -1) dpback[i][rind[region[i]]]++;
      |              ^~~~~~
regions.cpp:43:5: error: 'ende' was not declared in this scope
   43 |     ende[i] = c;
      |     ^~~~
regions.cpp: In function 'void dfsfront(int, std::vector<int>)':
regions.cpp:50:9: error: 'frontsolutions' was not declared in this scope
   50 |         frontsolutions[j][region[i]] += dpfront[j];
      |         ^~~~~~~~~~~~~~
regions.cpp:50:27: error: 'region' was not declared in this scope
   50 |         frontsolutions[j][region[i]] += dpfront[j];
      |                           ^~~~~~
regions.cpp:52:14: error: 'region' was not declared in this scope
   52 |     if (rind[region[i]]!=-1) dpfront[rind[region[i]]]++;
      |              ^~~~~~
regions.cpp:53:18: error: 'graph' was not declared in this scope; did you mean 'isgraph'?
   53 |     for (int ele:graph[i])
      |                  ^~~~~
      |                  isgraph
regions.cpp: In function 'int main()':
regions.cpp:71:5: error: 'graph' was not declared in this scope; did you mean 'isgraph'?
   71 |     graph.assign(n, vector<int>());
      |     ^~~~~
      |     isgraph
regions.cpp:72:10: error: request for member 'assign' in 'rind', which is of non-class type 'int'
   72 |     rind.assign(r, -1);
      |          ^~~~~~
regions.cpp:76:9: error: 'backsolutions' was not declared in this scope
   76 |         backsolutions[0][i] = 0;
      |         ^~~~~~~~~~~~~
regions.cpp:77:9: error: 'frontsolutions' was not declared in this scope
   77 |         frontsolutions[0][i] = 0;
      |         ^~~~~~~~~~~~~~
regions.cpp:82:12: error: 'region' was not declared in this scope
   82 |     cin >> region[0];
      |            ^~~~~~
regions.cpp:102:17: error: invalid types 'int[int]' for array subscript
  102 |             rind[i] = d++;
      |                 ^
regions.cpp:105:17: error: no matching function for call to 'std::vector<int>::clear(int)'
  105 |     rsum.clear(0);
      |                 ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from regions.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1498:7: note: candidate: 'void std::vector<_Tp, _Alloc>::clear() [with _Tp = int; _Alloc = std::allocator<int>]'
 1498 |       clear() _GLIBCXX_NOEXCEPT
      |       ^~~~~
/usr/include/c++/10/bits/stl_vector.h:1498:7: note:   candidate expects 0 arguments, 1 provided
regions.cpp:110:19: error: no matching function for call to 'std::vector<std::vector<int> >::clear(int)'
  110 |     dpback.clear(0);
      |                   ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from regions.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1498:7: note: candidate: 'void std::vector<_Tp, _Alloc>::clear() [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >]'
 1498 |       clear() _GLIBCXX_NOEXCEPT
      |       ^~~~~
/usr/include/c++/10/bits/stl_vector.h:1498:7: note:   candidate expects 0 arguments, 1 provided
regions.cpp:119:17: error: invalid types 'int[int]' for array subscript
  119 |         if (rind[a]!=-1) cout << frontsolutions[rind[a]][b] << endl;
      |                 ^
regions.cpp:119:34: error: 'frontsolutions' was not declared in this scope
  119 |         if (rind[a]!=-1) cout << frontsolutions[rind[a]][b] << endl;
      |                                  ^~~~~~~~~~~~~~
regions.cpp:119:53: error: invalid types 'int[int]' for array subscript
  119 |         if (rind[a]!=-1) cout << frontsolutions[rind[a]][b] << endl;
      |                                                     ^
regions.cpp:120:22: error: invalid types 'int[int]' for array subscript
  120 |         else if (rind[b]!=-1) cout << backsolutions[a][rind[b]] << endl;
      |                      ^
regions.cpp:120:39: error: 'backsolutions' was not declared in this scope
  120 |         else if (rind[b]!=-1) cout << backsolutions[a][rind[b]] << endl;
      |                                       ^~~~~~~~~~~~~
regions.cpp:120:60: error: invalid types 'int[int]' for array subscript
  120 |         else if (rind[b]!=-1) cout << backsolutions[a][rind[b]] << endl;
      |                                                            ^
regions.cpp:125:30: error: 'start' was not declared in this scope
  125 |                 s.push_back({start[ele], 2});
      |                              ^~~~~
regions.cpp:125:44: error: no matching function for call to 'std::vector<std::pair<int, short int> >::push_back(<brace-enclosed initializer list>)'
  125 |                 s.push_back({start[ele], 2});
      |                                            ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from regions.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, short int>; _Alloc = std::allocator<std::pair<int, short int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, short int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, short int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, short int>; _Alloc = std::allocator<std::pair<int, short int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, short int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, short int> >::value_type&&' {aka 'std::pair<int, short int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
regions.cpp:126:30: error: 'ende' was not declared in this scope
  126 |                 s.push_back({ende[ele], 0});
      |                              ^~~~
regions.cpp:126:43: error: no matching function for call to 'std::vector<std::pair<int, short int> >::push_back(<brace-enclosed initializer list>)'
  126 |                 s.push_back({ende[ele], 0});
      |                                           ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from regions.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, short int>; _Alloc = std::allocator<std::pair<int, short int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, short int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, short int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, short int>; _Alloc = std::allocator<std::pair<int, short int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, short int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, short int> >::value_type&&' {aka 'std::pair<int, short int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
regions.cpp:130:30: error: 'start' was not declared in this scope
  130 |                 s.push_back({start[ele], 1});
      |                              ^~~~~
regions.cpp:130:44: error: no matching function for call to 'std::vector<std::pair<int, short int> >::push_back(<brace-enclosed initializer list>)'
  130 |                 s.push_back({start[ele], 1});
      |                                            ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from regions.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, short int>; _Alloc = std::allocator<std::pair<int, short int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, short int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, short int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, short int>; _Alloc = std::allocator<std::pair<int, short int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, short int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, short int> >::value_type&&' {aka 'std::pair<int, short int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~