답안 #971541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971541	2024-04-28T19:59:57 Z	fzyzzz_z	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	컴파일 오류	0 ms	0 KB

garden

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

// void answer(int x) {
//     cout << "! " << x << '\n';
// }

using ll = long long; 

const int mxn = 150005; 

int g[2 * mxn], p[2 * mxn], vis[2 * mxn], c1[2 * mxn], val[2 * mxn]; 
vector<vector<int>> c2; 
vector<int> clen; 
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] += val[x];  
    for (auto u: r[x]) {
        dfs_c1(u, d + 1); 
    }
}
void dfs_c2(int x, int d, int f, int st) {
    c2[d] += val[x]; 
    while ((int) c2.back().size() >= d) c2.back().push_back(0); 
    // cout << "!! " << x << ' ' << d << ' ' << f << ' ' << val[x] << '\n';
    for (auto u: r[x]) {
        if (x == f && u == st) continue; 
        dfs_c2(u, d + 1, f, st); 
    }
}

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; 
        val[2 * i] = val[2 * i + 1] = 0; 
        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((int)adj[x].size(), 2) - 1]}]; 
        val[to[{x, adj[x][0]}]] = 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]]++; 
    }

    queue<int> q; 
    for (int i = 0; i < 2 * M; ++i) {
        if (p[i] == 0) {
            q.push(i); 
        }
    }
    while (q.size()) {
        auto x = q.front(); 
        q.pop(); 
        p[g[x]]--; 
        if (p[g[x]] == 0) {
            q.push(g[x]); 
        }
    }

    
    int co = 0; 
    for (auto x: c) if (p[x]) co++; 


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

            int cnt = 1; 
            int y = g[x]; 
            while (y != x) {
                y = g[y]; 
                cnt++; 
            }
            clen.push_back(cnt); 
            for (int i = 0; i + cnt < (int)c2.back().size(); ++i) {
                c2.back()[i + cnt] += c2.back()[i]; 
            }
        }
    }
    

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

        // int cans = 0; 
        // for (int st = 0; st < 2 * M; ++st) {
        //     if (val[st]) {
        //         int xx = st; 
        //         for (int t = 0; t < v; ++t) xx = g[xx]; 
        //         int ok = 0; 
        //         for (auto x: c) if (x == xx) ok = 1; 
        //         cans += ok; 
        //         // if (ok) cout << st << ' ';
        //     }
        // }
        // cout << "\n! " << cans << '\n'; 

        // cout << c1[v] << ' ' << c2[v] << '\n';

        int ans = 0; 
        if (v < 2 * M) ans = c1[v]; 

        for (int i = 0; i < (int) c2.size(); ++i) {
            int cl = clen[i]; 
            if (v < (int)c2[i].size()) ans += c2[i][v]; 
            else {
                int f = (v - 2 * M) / cl; 
                int vv = v - f * cl; 
                if (f > 0) vv += cl; 
                while (vv >= 2 * (int)c2[i].size()) vv -= cl; 
                ans += c2[i][vv]; 
            }
        }

        answer(ans); 
    }
}

// int main() {
//     int n, m, p, q; 
//     cin >> n >> m >> p >> q; 
//     int e[m][2], g[q]; 
//     for (int i = 0; i < m; ++i) cin >> e[i][0] >> e[i][1]; 
//     for (int i = 0; i < q; ++i) cin >> g[i]; 
//     count_routes(n, m, p, e, q, g); 
// }

Compilation message

garden.cpp: In function 'void dfs_c2(int, int, int, int)':
garden.cpp:34:11: error: no match for 'operator+=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} and 'int')
   34 |     c2[d] += val[x];
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int i = 1; i < adj[x].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
garden.cpp:65:41: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} and 'int')
   65 |         vis[x] = c1[x] = c2[x] = p[x] = 0;
      |                                         ^
In file included from /usr/include/c++/10/vector:72,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from garden.cpp:3:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator<int>]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'int' to 'const std::vector<int>&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from garden.cpp:3:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = int; _Alloc = std::allocator<int>]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'int' to 'std::vector<int>&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = int; _Alloc = std::allocator<int>]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'int' to 'std::initializer_list<int>'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~