Submission #1154243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154243		kes0716	Board Game (JOI24_boardgame)	C++20	0 / 100	277 ms	73028 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3009;
ll d1[MAXN], dist[MAXN][MAXN];
pair<int, int> d2[MAXN];
ll add[MAXN];
char stop[MAXN];
vector<int> graph[MAXN];
int main(){
    int n, m, K, i, j, a, b;
    scanf("%d %d %d", &n, &m, &K);
    for(i=0; i<m; i++){
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    scanf(" %s", stop + 1);
    memset(d1, 111, sizeof(d1));
    memset(d2, 111, sizeof(d2));
    queue<pair<int, int> > qa;
    for(i=1; i<=n; i++){
        if(stop[i] == '1')
            qa.push(make_pair(i, 0));
    }
    while(!qa.empty()){
        auto [v, d] = qa.front();
        //printf("v=%d d=%d\n", v, d);
        qa.pop();
        for(int u: graph[v]){
            if(d1[u] > d+1){
                d1[u] = d+1;
                qa.push(make_pair(u, d1[u]));
            }
        }
    }
    priority_queue<pair<pair<int, int>, int> , vector<pair<pair<int, int>, int> >, greater<pair<pair<int, int>, int> > > qb;
    for(i=1; i<=n; i++){
        if(stop[i] == '1'){
            bool flag = 0;
            for(int u: graph[i]){
                if(stop[u] == '1') flag = 1;
            }
            if(flag){
                qb.push({{0,0},0});
                d2[i] = make_pair(0, 0);
            }
        }
    }
    while(!qb.empty()){
        auto [d, v] = qb.top();
        qb.pop();
        if(d != d2[v]) continue;
        for(int u: graph[v]){
            if(stop[u] == '1'){
                pair<int, int> newdist = make_pair(d2[v].first, d2[v].second + 1);
                if(newdist < d2[u]){
                    qb.push({newdist, u});
                    d2[u] = newdist;
                }
            }
            else{
                pair<int, int> newdist = make_pair(d2[v].first + 1, d2[v].second);
                if(newdist < d2[u]){
                    qb.push({newdist, u});
                    d2[u] = newdist;
                }
            }
        }
    }
    int start;
    vector<int> players;
    scanf("%d", &start);
    for(i=2; i<=K; i++){
        int v;
        scanf("%d", &v);
        players.push_back(v);
    }
    for(i=1; i<=n; i++){
       // printf("i=%d d1=%d d2=(%d,%d)\n", i, d1[i], d2[i].first,d2[i].second);
        for(int j: players){
            if(i < d2[j].second)
                assert(2*(i-1) + d1[j] <= (d2[j].first + i));
            add[i] += min(2*(i-1) + d1[j], (ll)(d2[j].first + i));
        }
        //printf("add[%d]=%lld\n",i,add[i]);
    }
    memset(dist, 111, sizeof(dist));
    queue<pair<int, int> > q;
    q.push({start, 0});
    dist[start][0] = 0;
    while(!q.empty()){
        auto [v, c] = q.front();
        q.pop();
        for(int u: graph[v]){
            if(stop[u] == '1'){
                if(c >= n) continue;
                if(dist[u][c+1] > dist[v][c] + 1){
                    dist[u][c+1] = dist[v][c] + 1;
                    q.push({u, c+1});
                }
            }
            else{
                if(dist[u][c] > dist[v][c] + 1){
                    dist[u][c] = dist[v][c] + 1;
                    q.push({u, c});
                }
            }
        }
    }
    for(i=1; i<=n; i++){
        ll ans = LONG_LONG_MAX;
        if(stop[i] == '1'){
            for(j=1; j<=n; j++)
                ans = min(ans, dist[i][j] + add[j-1]);
        }
        for(j=0; j<=n; j++){
            ans = min(ans, dist[i][j] + add[j]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d %d", &n, &m, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf(" %s", stop + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d", &start);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 9
• Subtask 7: 0 / 23
• Subtask 8: 0 / 9