Submission #995534

#	Time	Username	Problem	Language	Result	Execution time	Memory
995534		bachhoangxuan	Spy 3 (JOI24_spy3)	C++17	100 / 100	58 ms	5532 KiB

Aoi

#include "Aoi.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pli pair<ll,int>
#define pii pair<int,int>
#define fi first
#define se second

namespace Aoi{
    const int maxn = 10005;
    const int maxm = 20005;
    const ll inf = 1e18;
    pli dist[maxn];
    vector<pii> edge[maxn];
    bool vis[maxn],del[maxm];
    int lst[maxn],f[maxm];

    string aoi(int N, int M, int Q, int K, vector<int> A, vector<int> B,
               vector<ll> C, vector<int> T, vector<int> X){
        for(int i=0;i<K;i++) del[X[i]]=true;
        for(int i=0;i<M;i++){
            edge[A[i]].push_back({B[i],i});
            edge[B[i]].push_back({A[i],i});
        }
        for(int i=0;i<N;i++) dist[i]={inf,-1};
        priority_queue<pli,vector<pli>,greater<pli>> pq;
        dist[0]={0,-1};pq.push({0,0});
        while(!pq.empty()){
            auto [d,u]=pq.top();pq.pop();
            if(dist[u].fi!=d) continue;
            for(auto [v,id]:edge[u]){
                pli nd={d+C[id],id};
                if(nd.fi<dist[v].fi) pq.push({nd.fi,v});
                dist[v]=min(dist[v],nd);
            }
        }
        vis[0]=true;
        for(int i=0;i<Q;i++){
            int u=T[i];
            while(!vis[u]){
                int id=dist[u].se;
                vis[u]=true;
                if(del[id]) f[id]=i+1;
                //cout << "dist " << u << ' ' << id << '\n';
                u^=A[id]^B[id];
            }
            lst[i]=u;
        }
        string S;
        for(int i=0;i<K;i+=10){
            ll num=0;
            for(int j=i;j<min(i+10,K);j++) num=num*(Q+1)+f[X[j]];
            for(int j=0;j<=40;j++) S+=char('0'+(num>>j&1));
        }
        for(int i=0;i<Q;i++){
            for(int j=0;j<14;j++) S+=char('0'+(lst[i]>>j&1));
        }
        return S;
    }
}

std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
                std::vector<int> B, std::vector<long long> C,
                std::vector<int> T, std::vector<int> X) {
    return Aoi::aoi(N,M,Q,K,A,B,C,T,X);
}

Bitaro

#include "Bitaro.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pli pair<ll,int>
#define pii pair<int,int>
#define fi first
#define se second


namespace Bitaro{
    const ll inf=1e18;
    const int maxn = 10005;
    const int maxm = 20005;
    int lst[maxn],f[maxm],up[maxn];
    pli dist[maxn];
    vector<pii> edge[maxn];

    void bitaro(int N, int M, int Q, int K,vector<int> A, vector<int> B,
            vector<ll> C, std::vector<int> T, std::vector<int> X,
            string S){
        for(int i=0;i<M;i++){
            edge[A[i]].push_back({B[i],i});
            edge[B[i]].push_back({A[i],i});
        }
        int P=0;
        for(int i=0;i<K;i+=10){
            ll num=0;
            for(int j=0;j<=40;j++) num+=(S[P++]-'0')*(1LL<<j);
            for(int j=min(i+10,K)-1;j>=i;j--){
                f[j]=num%(Q+1),num/=(Q+1);
                //cout << '*' << j << ' ' << f[j] << '\n';
            }
        }
        for(int i=0;i<N;i++) up[i]=-1;
        for(int i=0;i<Q;i++){
            for(int j=0;j<14;j++) lst[i]+=(S[P++]-'0')*(1<<j);
            for(int j=0;j<K;j++) C[X[j]]=(f[j]==i+1?1:inf);
            priority_queue<pli,vector<pli>,greater<pli>> pq;
            for(int j=0;j<N;j++) dist[j]={inf,-1};
            dist[lst[i]]={0,-1};
            pq.push({0,lst[i]});
            while(!pq.empty()){
                auto [d,u]=pq.top();pq.pop();
                if(dist[u].fi!=d) continue;
                //if(i==2) cout << "pq " << d << ' ' << u << '\n';
                for(auto [v,id]:edge[u]){
                    pli nd={d+C[id],id};
                    if(nd.fi<dist[v].fi) pq.push({nd.fi,v});
                    dist[v]=min(dist[v],nd);
                }
            }
            //if(i==2){
            //cout << T[i] << ' ' << lst[i] << '\n';
            //for(int j=0;j<N;j++) cout << dist[j].fi << ' ' << dist[j].se << '\n';
            //}
            //if(i!=2){
            int u=T[i];
            vector<int> ans;
            while(u!=0){
                if(up[u]==-1) up[u]=dist[u].se;
                ans.push_back(up[u]);
                //cout << '*' << u << ' ' << up[u] << '\n';
                u^=A[up[u]]^B[up[u]];
            }
            reverse(ans.begin(),ans.end());
            answer(ans);
            //}
        }
    }
}

void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
            std::vector<long long> C, std::vector<int> T, std::vector<int> X,
            std::string s) {
    Bitaro::bitaro(N,M,Q,K,A,B,C,T,X,s);
}

• Subtask 1: 100 / 100