답안 #971528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971528	2024-04-28T18:52:14 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;

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>> 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:37:24: error: expected unqualified-id before '>' token
   37 |     vector<vector<int>>> adj(N);
      |                        ^
garden.cpp:38:22: error: wrong number of template arguments (1, should be at least 2)
   38 |     map<pair<int, int>> to;
      |                      ^~
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:100:11: note: provided for 'template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map'
  100 |     class map
      |           ^~~
garden.cpp:42:11: error: invalid types 'int[<brace-enclosed initializer list>]' for array subscript
   42 |         to[{x, y}] = 2 * i;
      |           ^
garden.cpp:43:11: error: invalid types 'int[<brace-enclosed initializer list>]' for array subscript
   43 |         to[{y, x}] = 2 * i + 1;
      |           ^
garden.cpp:44:9: error: 'adj' was not declared in this scope
   44 |         adj[x].push_back(y);
      |         ^~~
garden.cpp:50:29: error: 'adj' was not declared in this scope
   50 |         for (int i = 1; i < adj[x].size(); ++i) {
      |                             ^~~
garden.cpp:51:17: error: invalid types 'int[<brace-enclosed initializer list>]' for array subscript
   51 |             g[to[{adj[x][i], x}]] = to[{x, adj[x][0]}];
      |                 ^
garden.cpp:51:39: error: invalid types 'int[<brace-enclosed initializer list>]' for array subscript
   51 |             g[to[{adj[x][i], x}]] = to[{x, adj[x][0]}];
      |                                       ^
garden.cpp:53:15: error: 'adj' was not declared in this scope
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |               ^~~
garden.cpp:53:13: error: invalid types 'int[<brace-enclosed initializer list>]' for array subscript
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |             ^
garden.cpp:53:35: error: invalid types 'int[<brace-enclosed initializer list>]' for array subscript
   53 |         g[to[{adj[x][0], x}]] = to[{x, adj[x][min(adj[x].size(), 2) - 1]}];
      |                                   ^