Submission #964899

#	Time	Username	Problem	Language	Result	Execution time	Memory
964899		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>

const int K = 200;
const int N = 200000;
const 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: In function 'void dfsback(int)':
regions.cpp:42:13: error: invalid types 'int[short int]' for array subscript
   42 |     if (rind[region[i]]!= -1) dpback[i][rind[region[i]]]++;
      |             ^
regions.cpp:42:45: error: invalid types 'int[short int]' for array subscript
   42 |     if (rind[region[i]]!= -1) dpback[i][rind[region[i]]]++;
      |                                             ^
regions.cpp: In function 'void dfsfront(int, std::vector<int>)':
regions.cpp:52:13: error: invalid types 'int[short int]' for array subscript
   52 |     if (rind[region[i]]!=-1) dpfront[rind[region[i]]]++;
      |             ^
regions.cpp:52:42: error: invalid types 'int[short int]' for array subscript
   52 |     if (rind[region[i]]!=-1) dpfront[rind[region[i]]]++;
      |                                          ^
regions.cpp: In function 'int main()':
regions.cpp:71:11: error: request for member 'assign' in 'graph', which is of non-class type 'std::vector<int> [200000]'
   71 |     graph.assign(n, vector<int>());
      |           ^~~~~~
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: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: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:60: error: invalid types 'int[int]' for array subscript
  120 |         else if (rind[b]!=-1) cout << backsolutions[a][rind[b]] << endl;
      |                                                            ^