Submission #964831

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964831	2024-04-17T15:52:27 Z	codefox	Regions (IOI09_regions)	C++14	Compilation error	0 ms	0 KB

regions

#include<bits/stdc++.h>

using namespace std;

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

#define ll long long
#define pii pair<int, short>

vector<vector<int>> graph;
vector<short> region;
vector<int> rind;

vector<int> start;
vector<int> ende;
int c =0 ;

vector<vector<int>> dpback;

vector<vector<ll>> backsolutions;
vector<vector<ll>> frontsolutions;

int K = 200;

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>());
    region.assign(n, 0);
    rind.assign(r, -1);
    start.assign(n, 0);
    ende.assign(n, 0);
    dpback.assign(n, vector<int>(K, 0));
    backsolutions.assign(r, vector<int>(K, -1));


    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);
    int d =0;
    for (int i = 0; i < n; i++) rsum[region[i]]++;
    for (int i = 0; i < r; i++)
    {
        if (rsum[i]> (n+K)/K) 
        {
            rind[i] = d++;
        }
    }

    rsum.resize(0);
    dfsback(0);
    dpback.resize(0);
    frontsolutions.assign(K, vector<int>(r, -1));
    dfsfront(0, vector<int>(K, 0));

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

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

    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:76:47: error: no matching function for call to 'std::vector<std::vector<long long int> >::assign(int&, std::vector<int>)'
   76 |     backsolutions.assign(r, vector<int>(K, -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:749:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<long long int>]'
  749 |       assign(size_type __n, const value_type& __val)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:749:47: note:   no known conversion for argument 2 from 'std::vector<int>' to 'const value_type&' {aka 'const std::vector<long long int>&'}
  749 |       assign(size_type __n, const value_type& __val)
      |                             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note: candidate: 'template<class _InputIterator, class> void std::vector<_Tp, _Alloc>::assign(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  768 |  assign(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note:   template argument deduction/substitution failed:
regions.cpp:76:47: note:   deduced conflicting types for parameter '_InputIterator' ('int' and 'std::vector<int>')
   76 |     backsolutions.assign(r, vector<int>(K, -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:794:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::initializer_list<_Tp>) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  794 |       assign(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:794:7: note:   candidate expects 1 argument, 2 provided
regions.cpp:108:48: error: no matching function for call to 'std::vector<std::vector<long long int> >::assign(int&, std::vector<int>)'
  108 |     frontsolutions.assign(K, vector<int>(r, -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:749:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<long long int>]'
  749 |       assign(size_type __n, const value_type& __val)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:749:47: note:   no known conversion for argument 2 from 'std::vector<int>' to 'const value_type&' {aka 'const std::vector<long long int>&'}
  749 |       assign(size_type __n, const value_type& __val)
      |                             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note: candidate: 'template<class _InputIterator, class> void std::vector<_Tp, _Alloc>::assign(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  768 |  assign(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note:   template argument deduction/substitution failed:
regions.cpp:108:48: note:   deduced conflicting types for parameter '_InputIterator' ('int' and 'std::vector<int>')
  108 |     frontsolutions.assign(K, vector<int>(r, -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:794:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::initializer_list<_Tp>) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  794 |       assign(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:794:7: note:   candidate expects 1 argument, 2 provided