Submission #1190112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190112		alexander707070	Spy 3 (JOI24_spy3)	C++20	0 / 100	5 ms	3028 KiB

Aoi

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

using namespace std;

namespace alice{

    const long long inf=1e17;
    
    int n,m,k,q,num;

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

    bool block[MAXN],vis[MAXN];
    long long dist[MAXN],cost[MAXN];

    int parent[MAXN],up[MAXN],where[MAXN],special[MAXN];

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

    void dijkstra(int x){
        for(int i=0;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});
            }
        }
    }

    int dfs(int x,int edge){

        vector<int> children;
        for(auto e:tree[x]){

            int y=dfs(e.first,e.second);
            if(y!=-1)children.push_back(y);
        }
        
        int ver=special[x];
        
        if(!children.empty() and ver==-1){
            ver=children.back();
            children.pop_back();
        }

        int last=ver;
        for(int i:children){
            comp[last]=num;
            comp[i]=num;

            last=num; num++;
        }

        if(x!=0 and block[edge]){
            where[edge]=last;
        }

        return last;
    }

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

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


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){
    using namespace alice;

    n=N; m=M; q=Q; k=K;
    num=q;

    for(int i=0;i<m;i++){
        v[A[i]].push_back({B[i],i});
        v[B[i]].push_back({A[i],i});

        cost[i]=C[i];
    }

    for(int i=0;i<n;i++)special[i]=-1;
    for(int i=0;i<T.size();i++)special[T[i]]=i;
    for(int i:X){
        block[i]=true; where[i]=31;
    }

    dijkstra(0);

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

    dfs(0,-1);
    comp[num-1]=0;

    for(int i=0;i<num;i++){
        ans+=tonum(comp[i],5);
    }

    for(int i=0;i<k;i++){
        ans+=tonum(where[X[i]],5);
    }

    return ans;
}

Bitaro

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

using namespace std;

namespace bob{
    const long long inf=1e17;
    
    int n,m,k,q,num;

    vector< pair<int,int> > v[MAXN];
    vector<int> comp[MAXN],used[MAXN];
    string ans;

    bool block[MAXN],vis[MAXN];
    long long dist[MAXN],cost[MAXN];

    int parent[MAXN],up[MAXN],where[MAXN],special[MAXN];

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

    void dijkstra(int x){
        for(int i=0;i<n;i++){
            dist[i]=inf; vis[i]=false;
        }
        
        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(int x){
        vector<int> res;
        while(x!=0){
            res.push_back(up[x]);
            x=parent[x];
        }

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

    void dfs(int x,int id){
        if(x<q)used[x].push_back(id);

        for(int i:comp[x]){
            dfs(i,id);
        }
    }

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

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

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){
    using namespace bob;

    n=N; m=M; q=Q; k=K;

    for(int i:X)block[i]=true;
    for(int i=0;i<n;i++)special[i]=-1;
    for(int i=0;i<T.size();i++)special[T[i]]=i;

    for(int i=0;i<m;i++){
        v[A[i]].push_back({B[i],i});
        v[B[i]].push_back({A[i],i});

        cost[i]=C[i];
    }

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

        if(curr!=0 and curr!=31)comp[curr].push_back(i);
    }

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

        where[i]=curr;
    }
    
    for(int i=0;i<k;i++){
        dfs(where[i],i);
    }


    for(int i=0;i<q;i++){
        for(int f:X)cost[f]=inf;
        for(int f:used[i])cost[X[f]]=0;

        dijkstra(0);

        answer(path(T[i]));
    }

    return;
}

• Subtask 1: 0 / 100