Submission #1040996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1040996	2024-08-01T13:41:00 Z	mdn2002	Board Game (JOI24_boardgame)	C++14	Compilation error	0 ms	0 KB

Main

/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n, m, k;
    string s;
    cin >> n >> m >> k;
    vector gr(n + 1,vector<int>());
    vector<int> X(n + 1), type(n + 1);
    vector con(n + 1, vector<long long>(k + 1, 1e9));
    con[0].assign(k + 1, 0);
    for (int i = 1; i <= m; i ++) {
        int x, y;
        cin >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    cin >> s;
    s.insert(s.begin(), '*');
    for (int i = 1; i <= k; i ++) cin >> X[i];
    for (int i = 1; i <= n; i ++) {
        if (s[i] == '0') continue;
        type[i] = 1;
        for (auto j : gr[i]) {
            if (s[j] == '1') type[i] = 2;
        }
    }
    for (int i = 2; i <= k; i ++) {
        vector<long long> dis(n + 1, 1e9);
        queue<pair<int, int>> q;
        vector<pair<int, long long>> nq;
        dis[X[i]] = 0;
        q.push({X[i], 0});

        int t = 0;
        while (t + 1 <= n) {
            while (q.size()) {
                auto [x, type] = q.front();
                q.pop();
                for (auto u : gr[x]) {
                    if (dis[u] > dis[x] + 1) {
                        dis[u] = dis[x] + 1;
                        if (s[u] == '0') q.push({u, 1});
                        else {
                            con[t + 1][i] = min(con[t + 1][i], dis[u]);
                            nq.push_back({u, dis[u]});
                        }
                    }
                }
                if (type == 0) dis[x] = 1e9;
            }
            if (nq.size() == 0) break;
            dis.assign(n + 1, 1e9);
            for (auto [x, y] : nq) {
                q.push({x, 0});
                dis[x] = min(dis[x], y);
            }
            nq.clear();
            t ++;
        }
    }
    vector<long long> dis(n + 1, 1e18), ans(n + 1, 1e18);
    queue<int> q, nq;
    dis[X[1]] = 0;
    q.push(X[1]);

    int t = 0;
    while (true) {
        long long add = 0;
        for (int i = 2; i <= k; i ++) add += con[t][i];
        while (q.size()) {
            int x = q.front();
            ans[x] = min(ans[x], dis[x] + add);
            q.pop();
            for (auto u : gr[x]) {
                if (dis[u] > dis[x] + 1) {
                    dis[u] = dis[x] + 1;
                    if (s[u] == '0') q.push(u);
                    else {
                        ans[u] = min(ans[u], dis[u] + add);
                        nq.push(u);
                    }
                }
            }
        }
        if (nq.size() == 0) break;
        q = nq;
        while (nq.size()) nq.pop();
        t ++;
    }

    for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
}
/*
5 5 2
1 2
2 3
2 4
3 5
4 5
01000
1 5

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

*/

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    for (int I = 0; I < T; I ++){
        solve();
    }
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:10:12: error: missing template arguments before 'gr'
   10 |     vector gr(n + 1,vector<int>());
      |            ^~
Main.cpp:12:12: error: missing template arguments before 'con'
   12 |     vector con(n + 1, vector<long long>(k + 1, 1e9));
      |            ^~~
Main.cpp:13:5: error: 'con' was not declared in this scope; did you mean 'cos'?
   13 |     con[0].assign(k + 1, 0);
      |     ^~~
      |     cos
Main.cpp:17:9: error: 'gr' was not declared in this scope
   17 |         gr[x].push_back(y);
      |         ^~
Main.cpp:26:23: error: 'gr' was not declared in this scope
   26 |         for (auto j : gr[i]) {
      |                       ^~
Main.cpp:40:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |                 auto [x, type] = q.front();
      |                      ^
Main.cpp:42:31: error: 'gr' was not declared in this scope
   42 |                 for (auto u : gr[x]) {
      |                               ^~
Main.cpp:45:55: error: no matching function for call to 'std::queue<std::pair<int, int> >::push(<brace-enclosed initializer list>)'
   45 |                         if (s[u] == '0') q.push({u, 1});
      |                                                       ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from Main.cpp:4:
/usr/include/c++/10/bits/stl_queue.h:265:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = std::pair<int, int>; _Sequence = std::deque<std::pair<int, int>, std::allocator<std::pair<int, int> > >; std::queue<_Tp, _Sequence>::value_type = std::pair<int, int>]'
  265 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:265:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
  265 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:270:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(std::queue<_Tp, _Sequence>::value_type&&) [with _Tp = std::pair<int, int>; _Sequence = std::deque<std::pair<int, int>, std::allocator<std::pair<int, int> > >; std::queue<_Tp, _Sequence>::value_type = std::pair<int, int>]'
  270 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:270:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::queue<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
  270 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
Main.cpp:48:53: error: no matching function for call to 'std::vector<std::pair<int, long long int> >::push_back(<brace-enclosed initializer list>)'
   48 |                             nq.push_back({u, dis[u]});
      |                                                     ^
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 Main.cpp:4:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, long long int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, long long int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, long long int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, long long int> >::value_type&&' {aka 'std::pair<int, long long int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
Main.cpp:56:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |             for (auto [x, y] : nq) {
      |                       ^
Main.cpp:77:27: error: 'gr' was not declared in this scope
   77 |             for (auto u : gr[x]) {
      |                           ^~