Submission #759403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
759403	2023-06-16T09:14:43 Z	yellowtoad	Werewolf (IOI18_werewolf)	C++17	Compilation error	0 ms	0 KB

werewolf

#include "werewolf.h"
#include <iostream>
#include <vector>
#define f first
#define s 
#define int long long
using namespace std;

int n, m, q, p[200010], id[200010], pmax[600010][21], pmin[600010][21], vmax[600010], vmin[600010], mxsz, mnsz, cnt;
pair<int,int> rmax[600010], rmin[600010];
vector<int> edge[200010], maxx[600010], minn[600010], node[800010];

int dsu(int u) {
    if (p[u] == u) return u;
    return (p[u] = dsu(p[u]));
}

void buildmax(int u) {
    int v = pmax[u][0];
    for (int i = 1; i <= 20; i++) {
        if (v == -1) break;
        pmax[u][i] = pmax[v][i-1];
        v = pmax[u][i];
    }
    if (maxx[u].empty()) {
        ++cnt;
        rmax[u] = {cnt,cnt};
        return;
    }
    for (int i = 0; i < maxx[u].size(); i++) {
        buildmax(maxx[u][i]);
        rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
    }
}

void buildmin(int u) {
    int v = pmin[u][0];
    for (int i = 1; i <= 20; i++) {
        if (v == -1) break;
        pmin[u][i] = pmin[v][i-1];
        v = pmin[u][i];
    }
    if (minn[u].empty()) {
        node[1].push_back(rmax[u].f);
        rmin[u] = {cnt,cnt};
        cnt++;
        return;
    }
    for (int i = 0; i < minn[u].size(); i++) {
        buildmin(minn[u][i]);
        rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
    }
}

std::vector<signed> check_validity(signed N, std::vector<signed> X, std::vector<signed> Y, std::vector<signed> S, std::vector<signed> E, std::vector<signed> L, std::vector<signed> R) {
    vector<int> ans;
    n = N; m = X.size(); q = S.size();
    for (int i = 0; i < m; i++) {
        edge[X[i]].push_back(Y[i]);
        edge[Y[i]].push_back(X[i]);
    }
    for (int i = 0; i < n+m; i++) for (int j = 0; j <= 20; j++) pmax[i][j] = pmin[i][j] = -1;
    for (int i = 0; i < n; i++) p[i] = id[i] = vmin[i] = i;
    mnsz = n-1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < edge[i].size(); j++) {
            if (edge[i][j] < i) {
                int u = edge[i][j], v = i;
                if (p[dsu(u)] != p[dsu(v)]) {
                    ++mnsz;
                    pmin[id[p[dsu(u)]]][0] = pmin[id[p[dsu(v)]]][0] = mnsz;
                    minn[mnsz].push_back(id[p[dsu(u)]]);
                    minn[mnsz].push_back(id[p[dsu(v)]]);
                    p[dsu(v)] = p[dsu(u)];
                    id[p[dsu(u)]] = mnsz;
                    vmin[mnsz] = i;
                }
            }
        }
    }
    mxsz = n-1;
    for (int i = 0; i < n; i++) p[i] = id[i] = vmax[i] = i;
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < edge[i].size(); j++) {
            if (edge[i][j] > i) {
                int u = edge[i][j], v = i;
                if (p[dsu(u)] != p[dsu(v)]) {
                    ++mxsz;
                    pmax[id[p[dsu(u)]]][0] = pmax[id[p[dsu(v)]]][0] = mxsz;
                    maxx[mxsz].push_back(id[p[dsu(u)]]);
                    maxx[mxsz].push_back(id[p[dsu(v)]]);
                    p[dsu(v)] = p[dsu(u)];
                    id[p[dsu(u)]] = mxsz;
                    vmax[mxsz] = i;
                }
            }
        }
    }
    for (int i = 0; i <= mxsz; i++) rmax[i] = {1e9,-1e9};
    for (int i = 0; i <= mnsz; i++) rmin[i] = {1e9,-1e9};
    buildmax(mxsz);
    cnt = 0;
    buildmin(mnsz);
    for (int _ = 0; _ < q; _++) {
        int u = S[_], v = E[_], l = L[_], r = R[_];
        for (int j = 20; j >= 0; j--) if (vmax[pmax[u][j]] >= l) u = pmax[u][j];
        for (int j = 20; j >= 0; j--) if ((pmin[v][j] != -1) && (vmin[pmin[v][j]] <= r)) v = pmin[v][j];
        for (int i = rmin[v].f; i <= rmin[v].s; i++) {
            if ((rmax[u].f <= node[1][i]) && (node[1][i] <= rmax[u].s)) {
                ans.push_back(1);
                goto skip;
            }
        }
        ans.push_back(0);
        skip:;
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'void buildmax(long long int)':
werewolf.cpp:30:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < maxx[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
werewolf.cpp:32:67: error: expected unqualified-id before ',' token
   32 |         rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
      |                                                                   ^
werewolf.cpp:32:86: error: expected unqualified-id before ')' token
   32 |         rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
      |                                                                                      ^
werewolf.cpp:32:87: error: no match for 'operator=' (operand types are 'std::pair<long long int, long long int>' and '<brace-enclosed initializer list>')
   32 |         rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
      |                                                                                       ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from werewolf.h:3,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long long int, long long int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long long int, long long int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, long long int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long long int, long long int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long long int, long long int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, long long int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
werewolf.cpp:32:87: note:   couldn't deduce template parameter '_U1'
   32 |         rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
      |                                                                                       ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from werewolf.h:3,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
werewolf.cpp:32:87: note:   couldn't deduce template parameter '_U1'
   32 |         rmax[u] = {min(rmax[u].f,rmax[maxx[u][i]].f),max(rmax[u].s,rmax[maxx[u][i]].s)};
      |                                                                                       ^
werewolf.cpp: In function 'void buildmin(long long int)':
werewolf.cpp:49:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < minn[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
werewolf.cpp:51:67: error: expected unqualified-id before ',' token
   51 |         rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
      |                                                                   ^
werewolf.cpp:51:86: error: expected unqualified-id before ')' token
   51 |         rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
      |                                                                                      ^
werewolf.cpp:51:87: error: no match for 'operator=' (operand types are 'std::pair<long long int, long long int>' and '<brace-enclosed initializer list>')
   51 |         rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
      |                                                                                       ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from werewolf.h:3,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long long int, long long int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long long int, long long int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, long long int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long long int, long long int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long long int, long long int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, long long int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
werewolf.cpp:51:87: note:   couldn't deduce template parameter '_U1'
   51 |         rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
      |                                                                                       ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from werewolf.h:3,
                 from werewolf.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
werewolf.cpp:51:87: note:   couldn't deduce template parameter '_U1'
   51 |         rmin[u] = {min(rmin[u].f,rmin[minn[u][i]].f),max(rmin[u].s,rmin[minn[u][i]].s)};
      |                                                                                       ^
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:66:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j = 0; j < edge[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
werewolf.cpp:84:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int j = 0; j < edge[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
werewolf.cpp:108:47: error: expected unqualified-id before ';' token
  108 |         for (int i = rmin[v].f; i <= rmin[v].s; i++) {
      |                                               ^
werewolf.cpp:109:70: error: expected unqualified-id before ')' token
  109 |             if ((rmax[u].f <= node[1][i]) && (node[1][i] <= rmax[u].s)) {
      |                                                                      ^
werewolf.cpp:117:12: error: could not convert 'ans' from 'vector<long long int>' to 'vector<int>'
  117 |     return ans;
      |            ^~~
      |            |
      |            vector<long long int>