Submission #971529

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
971529	2024-04-28T18:52:53 Z	fzyzzz_z	Tropical Garden (IOI11_garden)	C++17	Compilation error	0 ms	0 KB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

const int mxn = 150005; 

int g[2 * mxn], p[2 * mxn], vis[2 * mxn], c1[2 * mxn], c2[2 * mxn]; 
vector<int> r[2 * mxn]; 

void dfs_find(int x) {
    if (vis[x]) return; 
    vis[x] = 1; 
    for (auto u: r[x]) {
        dfs_find(u); 
    }
    dfs_find(g[x]); 
}
void dfs_c1(int x, int d) {
    c1[d]++; 
    for (auto u: r[x]) {
        dfs_c1(u, d + 1); 
    }
}
void dfs_c2(int x, int d, int f) {
    c2[d]++; 
    for (auto u: r[x]) {
        if (u != f) {
            dfs_c2(u, d + 1, f); 
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    vector<vector<int>> adj(N); 
    map<pair<int, int>, int> to; 
    vector<int> c; 
    for (int i = 0; i < M; ++i) {
        int x = R[i][0], y = R[i][1]; 
        to[{x, y}] = 2 * i; 
        to[{y, x}] = 2 * i + 1; 
        adj[x].push_back(y); 
        adj[y].push_back(x); 
        if (x == P) c.push_back(2 * i + 1); 
        if (y == P) c.push_back(2 * i); 
    }
    for (int x = 0; x < N; ++x) {
        for (int i = 1; i < adj[x].size(); ++i) {
            g[to[{adj[x][i], x}]] = to[{x, adj[x][0]}]; 
        }
        g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}]; 
    }
    for (int x = 0; x < 2 * M; ++x) {
        vis[x] = c1[x] = c2[x] = p[x] = 0; 
    }
    for (int x = 0; x < 2 * M; ++x) {
        r[g[x]].push_back(x); 
        p[g[x]]++; 
    }

    dfs_find(c[0]); 
    for (auto x: c) assert(vis[x]); 
    queue<int> q; 
    for (int i = 0; i < 2 * M; ++i) {
        if (vis[i] && p[i] == 0) {
            q.push(i); 
        }
    }
    while (q.size()) {
        auto x = q.front(); 
        assert(vis[x]); 
        q.pop(); 
        p[g[x]]--; 
        if (p[g[x]] == 0) {
            q.push(g[x]); 
        }
    }
    for (int x = 0; x < 2 * M; ++x) if (vis[x]) assert(p[x] == 1 || p[x] == 0); 
    int co = 0; 
    for (auto x: c) if (p[x]) co++; 
    assert(co == 2); 

    for (auto x: c) {
        if (p[x] == 0) {
            dfs_c1(x, 0); 
        } else {
            dfs_c2(x, 0, g[x]); 
        }
    }

    int clen = 0; 
    for (int i = 0; i < 2 * M; ++i) {
        if (vis[i] && p[i]) clen++; 
    }

    for (int i = 0; i < 2 * M; ++i) {
        if (i + clen < 2 * M) {
            c2[i + clen] += c2[i]; 
        }
    }

    for (int i = 0; i < Q; ++i) {
        int v = G[i] - 1; 

        if (v < 2 * M) {
            answer(c1[v] + c2[v]); 
        } else {
            int f = (v - 2 * M) / clen; 
            v -= f * clen; 
            if (f > 0) v += clen; 
            while (v >= 2 * M) v -= clen; 
            answer(c2[v]); 
        }
    }


}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int i = 1; i < adj[x].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
garden.cpp:53:67: error: no matching function for call to 'min(std::vector<int>::size_type, int)'
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |                                                                   ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from garden.cpp:3:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
garden.cpp:53:67: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |                                                                   ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from garden.cpp:3:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
garden.cpp:53:67: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from garden.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
garden.cpp:53:67: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |                                                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from garden.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
garden.cpp:53:67: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |                                                                   ^
garden.cpp:53:35: error: no match for 'operator[]' (operand types are 'std::map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |                                   ^
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from garden.cpp:3:
/usr/include/c++/10/bits/stl_map.h:492:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  492 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:492:34: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
  492 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_map.h:512:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  512 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:512:29: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::map<std::pair<int, int>, int>::key_type&&' {aka 'std::pair<int, int>&&'}
  512 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~