제출 #1317514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317514		goodpjw2008	Board Game (JOI24_boardgame)	C++20	59 / 100	4094 ms	7244 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define x first
#define y second
#define int long long
using namespace std;
using pii = pair<int,int>;
vector<int>v[50005];
int c[50005],type[50005],distfrom1[50005],distfrom2[50005],from[50005],ans[50005],csum[50005],dist[50005];
bool chk[50005];
struct p{
    int idx,cnt,val,jump;
    bool operator<(const p &b)const{
        if(val==b.val)return cnt>b.cnt;
        return val>b.val;
    }
};
struct pp{
    int idx,from,val;
};
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,k,x,y,s;
    string str;
    cin>>n>>m>>k;
    for(int i = 0; i < m; i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    cin>>str>>s;
    str="0"+str;
    for(int i = 1; i <= n; i++){
        if(str[i]=='1'){
            bool f=0;
            for(int &nx:v[i]){
                if(str[nx]=='1'){
                    f=1;
                    break;
                }
            }
            if(f)type[i]=2;
            else type[i]=1;
        }
    }
    queue<pp>qq;
    for(int i = 1; i <= n; i++){
        if(type[i]==1){
            chk[i]=1;
            qq.push({i,i,0});
        }
    }
    if(qq.empty()){
        memset(distfrom1,0x3f,sizeof(distfrom1));
    }
    while(!qq.empty()){
        pp now=qq.front();qq.pop();
        distfrom1[now.idx]=now.val;
        for(int &nx:v[now.idx]){
            if(!chk[nx]){
                chk[nx]=1;
                from[nx]=now.from;
                qq.push({nx,now.from,now.val+1});
            }
        }
    }
    deque<int>q;
    memset(distfrom2,0x3f,sizeof(distfrom2));
    for(int i = 1; i <= n; i++){
        if(type[i]==2){
            q.push_back(i);
            distfrom2[i]=0;
        }
    }
    while(!q.empty()){
        int now=q.front();q.pop_front();
        for(int &nx:v[now]){
            if(type[now]!=1){
                if(distfrom2[nx]>distfrom2[now]+1){
                    distfrom2[nx]=distfrom2[now]+1;
                    q.push_back(nx);
                }
            }
            else{
                if(distfrom2[nx]>distfrom2[now]){
                    distfrom2[nx]=distfrom2[now];
                    q.push_front(nx);
                }
            }
        }
    }
    for(int i = 1; i < k; i++){
        cin>>x;
        if(distfrom2[x]>=1e18){
            if(!type[x]){
                c[1]+=distfrom1[x];
                c[2]+=-distfrom1[x]+2;
            }
            else{
                c[1]+=2;
            }
            continue;
        }
        if(distfrom1[x]>=1e18){
            if(!type[x]){
                c[1]+=distfrom2[x];
                c[2]+=-distfrom2[x]+1;
            }
            else{
                c[1]+=1;
            }
            continue;
        }
        if(!type[x]){
            if(distfrom1[x]>=distfrom2[x]){
                c[1]+=distfrom2[x];
                c[2]+=-distfrom2[x]+1;
            }
            else{
                int bv=distfrom2[x];
                c[1]+=distfrom1[x];
                c[2]+=-distfrom1[x]+2;
                c[min(n+1,2+bv-distfrom1[x])]+=-1;
            }
        }
        else if(type[x]==1){
            c[1]+=2;
            c[distfrom2[x]]+=-1;
        }
        else{
            c[1]+=1;
        }
    }
    int add=0;
    for(int i = 1; i <= n; i++){
        add+=c[i];
        c[i]=add;
        csum[i]=csum[i-1]+c[i];
        ans[i]=1e18;
        dist[i]=1e18;
    }
    //for(int i = 1; i <= n; i++)cerr<<distfrom1[i]<<' ';
    //cerr<<'\n';
    //for(int i = 1; i <= n; i++)cerr<<distfrom2[i]<<' ';
    //cerr<<'\n';
    //for(int i = 1; i <= n; i++)cerr<<c[i]<<' ';
    priority_queue<p>pq;
    pq.push({s,0,0,0});
    while(!pq.empty()){
        p cur=pq.top();pq.pop();
        if(cur.cnt>n)continue;
        bool skip=0;
        ans[cur.idx]=min(ans[cur.idx],cur.val);
        if(cur.jump){
            pq.push({cur.idx,cur.cnt,cur.val+c[cur.cnt],0});
            continue;
        }
        if(dist[cur.idx]<=cur.val-csum[cur.cnt])continue;
        dist[cur.idx]=cur.val-csum[cur.cnt];
        if(cur.jump)cur.val+=c[cur.cnt];
        for(int &nx:v[cur.idx]){
            if(type[nx]){
                pq.push({nx,cur.cnt+1,cur.val+1,1});
            }
            else{
                pq.push({nx,cur.cnt,cur.val+1,0});
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout<<ans[i]<<'\n';
    }
}

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