Submission #1216379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216379		Hora000	Board Game (JOI24_boardgame)	C++20	17 / 100	2386 ms	6924 KiB

Main

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

long long n, m, k;
string stop;
vector<vector<long long>> g;
vector<long long> dist1, dist2;
queue<long long> q1, q2;
vector<long long> start;
vector<long long> ans;
vector<array<long long, 3>> stopw; //alaptav, egyesek, kettesek


void bfs(bool second, queue<long long>& q, vector<long long>& dist){
    if(second){
        for(long long i = 1; i <= n; i++){
            if(stop[i] == '1'){
                q.push(i);
                dist[i] = 0;
            }
            else dist[i] = -1;
        }
    }
    if(q.empty()){
        fill(dist.begin(), dist.end(), LLONG_MAX / 2);
    }
    vector<bool> qin(n + 1, false);
    while(!q.empty()){
        long long v = q.front();
        q.pop();
        for(auto x : g[v]){
            if(second && stop[v] == '1' && stop[x] == '1' && !(qin[x] && qin[v])){
                if(!qin[x]){
                    q1.push(x);
                    dist1[x] = 0;
                    qin[x] = true;
                }
                if(!qin[v]){
                    q1.push(v);
                    dist1[v] = 0;
                    qin[v] = true; 
                }
            }
            if(!second && stop[x] == '1') continue;
            if(dist[x] < 0){
                dist[x] = dist[v] + 1;
                q.push(x);
            }
        }
    }
    if(!second) for(long long i = 1; i <= n; i++) dist[i] = max(dist[i], (long long)1);
    if(second){
        for(long long i = 1; i <= n; i++) if(dist[i] == 0) dist[i] = 2;
        bfs(false, q1, dist1);
    }
}

void prepare(){
    for(long long j = 2; j < start.size(); j++){
        long long i = start[j];
        if(dist1[i] <= dist2[i]){
            stopw[1][1]++;
            stopw[1][0] += dist1[i];
        }
        else{
            stopw[1][2]++;
            stopw[1][0] += dist2[i];       
        }

        if(1 <= dist1[i] - dist2[i] && dist1[i] - dist2[i] + 1 < stopw.size()){
            stopw[dist1[i] - dist2[i]][2]--;
            stopw[dist1[i] - dist2[i]][1]++;
            stopw[dist1[i] - dist2[i] + 1][0] -= dist2[i] + (dist1[i] - dist2[i] - 1);
            stopw[dist1[i] - dist2[i] + 1][0] += dist1[i];
        }
    }

    for(long long i = 1; i <= n; i++){
        stopw[i][0] += stopw[i - 1][0] + stopw[i - 1][1] + stopw[i - 1][2] * 2;
        stopw[i][1] += stopw[i - 1][1];
        stopw[i][2] += stopw[i - 1][2];
    }
}

void prepare2(){
    for(int j = 2; j < start.size(); j++){
        int i = start[j];
        for(int h = 1; h < stopw.size(); h++){
            stopw[h][0] += min((h - 1) * 2 + dist2[i], h - 1 + dist1[i]);
        }
    }
}

void dijkstra(){
    priority_queue<array<long long, 3>> pq; //tav, stops, v
    pq.push({0, 0, start[1]});
    vector<long long> dist(n + 1, -1);
    while(!pq.empty()){
        auto [d, s, v] = pq.top();
        pq.pop();
        d *= -1;
        if(dist[v] != -1) continue;
        dist[v] = d;
        for(auto x : g[v]){
            if(stop[v] == '1' && v != start[1]){
                pq.push({-(d + 1 + stopw[s + 1][0] - stopw[s][0]), s + 1, x});
            }
            else{
                pq.push({-(d + 1), s, x});
            }
        }
    }
    for(long long i = 1; i <= n; i++) cout << dist[i] << "\n";
}

int main(){
    cin >> n >> m >> k;
    g.resize(n + 1);
    start.resize(k + 1);
    dist1.resize(n + 1, -1);
    dist2.resize(n + 1, -1);
    ans.resize(n + 1);
    stopw.resize(n + 1);
    for(long long i = 0; i < m; i++){
        long long a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> stop;
    stop = '2' + stop;
    for(long long i = 1; i <= k; i++) cin >> start[i];
    bfs(true, q2, dist2);
    prepare2();
    dijkstra();
}

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