Submission #1189574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189574		alexander707070	Spy 3 (JOI24_spy3)	C++20	0 / 100	124 ms	10524 KiB

Aoi

#include<bits/stdc++.h>
#define MAXN 20007
#include "Aoi.h"

using namespace std;

const long long inf=1e17;

int n,m,k,q,parent[MAXN],up[MAXN],where[MAXN];

long long cost[MAXN],dist[MAXN];

vector< pair<int,int> > v[MAXN],tree[MAXN];

bool vis[MAXN],special[MAXN],rem[MAXN];
string ans;

priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > pq;

void dijkstra(int x){
    for(int i=1;i<=n;i++)dist[i]=inf;
    dist[x]=0;

    pq.push({dist[x],x});

    while(!pq.empty()){
        int minv=pq.top().second;
        pq.pop();

        if(vis[minv])continue;
        vis[minv]=true;

        for(auto e:v[minv]){
            if(vis[e.first] or dist[e.first]<=dist[minv]+cost[e.second])continue;

            dist[e.first]=dist[minv]+cost[e.second];
            
            parent[e.first]=minv;
            up[e.first]=e.second;

            pq.push({dist[e.first],e.first});
        }
    }
}

vector<int> path;

string num(int x,int bits){    
    string res;

    for(int i=0;i<bits;i++){
        res.push_back(x%2+'0');
        x/=2;
    }

    reverse(res.begin(),res.end());

    return res;
}

void dfs(int x){    
    if(special[x])where[x]=path.back();

    for(auto e:tree[x]){

        if(rem[e.second]){
            up[e.second]=path.back();
            path.push_back(e.second);
        }

        dfs(e.first);

        if(rem[e.second])path.pop_back();
    }
}

string aoi(int N, int M, int Q, int K, vector<int> A,vector<int> B, vector<long long> C,vector<int> T, vector<int> X){
    n=N; m=M; q=Q; k=K;

    for(int i=1;i<=q;i++){
        special[T[i-1]+1]=true;
    }

    for(int i:X)rem[i+1]=true;
    
    for(int i=1;i<=m;i++){
        v[A[i-1]+1].push_back({B[i-1]+1,i});
        v[B[i-1]+1].push_back({A[i-1]+1,i});
    }

    for(int i=1;i<=m;i++)cost[i]=C[i-1];

    dijkstra(1);
    
    for(int i=2;i<=n;i++){
        tree[parent[i]].push_back({i,up[i]});
    }

    path={0};
    dfs(1);

    for(int i=1;i<=q;i++){
        ans+=num(where[T[i-1]+1],9);
    }

    for(int i=1;i<=k;i++){
        ans+=num(up[X[i-1]+1],9);
    }

    return ans;
}

Bitaro

#include<bits/stdc++.h>
#define MAXN 20007
#include "Bitaro.h"

using namespace std;

const long long inff=1e17;

int nn,mm,kk,qt;

int comp[MAXN],par[MAXN],who[MAXN];
bool miss[MAXN];

vector< pair<int,int> > w[MAXN];
vector<int> t[MAXN];

long long edge[MAXN],dst[607][MAXN];
pair<int,int> to[607][MAXN];

bool used[MAXN];
vector<int> qs[MAXN];

priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > qq;

void dijkstra(int id,int x){
    for(int i=1;i<=nn;i++){
        used[i]=false; dst[id][i]=inff;
    }
    dst[id][x]=0;

    qq.push({dst[id][x],x});

    while(!qq.empty()){
        int minv=qq.top().second;
        qq.pop();

        if(used[minv])continue;
        used[minv]=true;

        for(auto e:w[minv]){
            if(used[e.first] or dst[id][e.first]<=dst[id][minv]+edge[e.second])continue;

            dst[id][e.first]=dst[id][minv]+edge[e.second];
            to[id][e.first]={minv,e.second};

            qq.push({dst[id][e.first],e.first});
        }
    }
}

vector<int> sol[MAXN];
pair<int,int> z[MAXN];

vector<int> route(int id,int x){
    vector<int> s;

    while(to[id][x].first!=0){
        s.push_back(to[id][x].second);
        x=to[id][x].first;
    }

    reverse(s.begin(),s.end());
    return s;
}

vector<int> mergev(vector<int> x,vector<int> y){
    for(int i=0;i<y.size();i++){
        x.push_back(y[i]);
    }

    return x;
}

void fix(int x){
    int from=0;
    if(x==0)from=0;
    else from=x+kk;

    for(int i:t[x]){

        if(dst[from][z[i].second] < dst[from][z[i].first]){
            swap(z[i].first,z[i].second);
            for(int f=1;f<=nn;f++){
                swap(dst[i][f],dst[i+kk][f]);
                swap(to[i][f],to[i+kk][f]);
            }
        }

        fix(i);
    }
}

void solve(int x,vector<int> path){
    int id=0;
    if(x>0)id=kk+x;

    for(int i:qs[x]){
        sol[i]=mergev(path,route(id,i));
    }

    for(int i:t[x]){
        solve(i,mergev( mergev(path,route(id,z[i].first)) , {who[i]}) );
    }
}

void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B,vector<long long> C, vector<int> T, vector<int> X,string s){
    nn=N; mm=M; kk=K; qt=Q;

    for(int i:X)miss[i+1]=true;

    for(int i=1;i<=mm;i++){
        if(miss[i])continue;

        w[A[i-1]+1].push_back({B[i-1]+1,i});
        w[B[i-1]+1].push_back({A[i-1]+1,i});

        edge[i]=C[i-1];
    }

    z[0]={1,1};
    dijkstra(0,1);

    for(int i=0;i<X.size();i++){
        z[i+1]={A[X[i]]+1,B[X[i]]+1};

        dijkstra(i+1,A[X[i]]+1);
        dijkstra(i+1+kk,B[X[i]]+1);

        who[i+1]=X[i]+1;
    }

    for(int i=0;i<9*qt;i+=9){
        int curr=0;

        for(int f=i;f<i+9;f++){
            curr*=2; curr+=s[f]-'0';
        }

        qs[curr].push_back(T[i/9]+1);
    }

    for(int i=qt*9;i<s.size();i+=9){
        int curr=0;

        for(int f=i;f<i+9;f++){
            curr*=2; curr+=s[f]-'0';
        }

        par[(i-9*qt)/9+1]=curr;
    }

    for(int i=1;i<=kk;i++){
        t[par[i]].push_back(i);
    }
    
    fix(0);
    solve(0,{});

    for(int i:T){
        for(int &f:sol[i+1])f--;
        answer(sol[i+1]);
    }

    return;
}

• Subtask 1: 0 / 100