Submission #1017818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017818		isaachew	Spy 3 (JOI24_spy3)	C++17	96 / 100	109 ms	6228 KiB

Aoi

#include "Aoi.h"
#include <bits/stdc++.h>
/*
 Send the "shortest path tree of targets" along with which edges are used
 */
namespace {
std::vector<int> parents,parentedges;
std::vector<std::vector<int>> children;
std::vector<std::vector<std::pair<int,int>>> edges;
std::vector<int> targets;
std::vector<int> missinginds;
std::vector<int> reaches;
std::vector<int> ereaches;
int dfs(int cur){
    int dpset=0;
    
    for(int i=0;i<targets.size();i++){
        if(targets[i]==cur){
            dpset|=(1<<i);
            reaches.push_back(dpset);
        }
    }
    for(int i:children[cur]){
        int oset=dfs(i);
        if(oset!=0&&dpset!=0){
            reaches.push_back(oset|dpset);
        }
        dpset|=oset;
    }
    if(cur){
        int eind=missinginds[parentedges[cur]];
        if(eind>=0){
            ereaches[eind]=dpset;
        }
    }
    return dpset;
}
}

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) {
    targets=T;
    missinginds.resize(M,-1);
    for(int i=0;i<K;i++)missinginds[X[i]]=i;
    parents.resize(N);
    parentedges.resize(N);
    children.resize(N);
    edges.resize(N);
    ereaches.resize(M);
    for(int i=0;i<M;i++){
        edges[A[i]].push_back({B[i],i});
        edges[B[i]].push_back({A[i],i});
    }
    std::vector<long long> dists(N,1e18);
    std::priority_queue<std::pair<long long,std::pair<int,int>>> dijkstra;
    dijkstra.push({0,{-1,0}});//(-dist, (edgenum,index))
    while(!dijkstra.empty()){
        std::pair<long long,std::pair<int,int>> cur=dijkstra.top();
        dijkstra.pop();
        cur.first=-cur.first;
        int edgenum=cur.second.first;
        int curnode=cur.second.second;
        if(dists[curnode]<=cur.first)continue;
        dists[curnode]=cur.first;
        if(curnode){
            parents[curnode]=A[edgenum]^B[edgenum]^curnode;
            parentedges[curnode]=edgenum;
            children[parents[curnode]].push_back(curnode);
        }
        for(std::pair<int,int> i:edges[curnode]){
            dijkstra.push({-(cur.first+C[i.second]),{i.second,i.first}});
        }
    }
    dfs(0);
    
  std::string s(1600, '0');
    std::vector<int> stk;
    std::vector<int> nreaches;
    int ind=0;
    for(int i:reaches){
        if(i==0)continue;
        if(i==(i&-i)){
            stk.push_back(i);
            nreaches.push_back(i);
            s[ind++]='0';
            for(int j=0;j<4;j++){
                int cbit=__builtin_ctz(i);
                s[ind++]=((cbit>>j)&1)|'0';
            }
        }else{
            while(stk.back()!=i){
                int last=stk.back();
                stk.pop_back();
                stk.back()|=last;
                nreaches.push_back(stk.back());
                s[ind++]='1';
            }
        }
    }
    for(int i=0;i<K;i++){
        int creach=31;
        for(int j=0;j<nreaches.size();j++){
            if(ereaches[i]==nreaches[j]){
                creach=j;
                break;
            }
        }
        for(int j=0;j<5;j++){
            s[ind++]=((creach>>j)&1)|'0';
        }
    }
  return s;
}

Bitaro

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

namespace {

}  // namespace

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) {
    std::vector<std::vector<std::pair<int,int>>> edges(N);
    std::vector<int> stk,rch,missinginds(M);
    std::vector<int> mreach(M,2*Q-2);
    for(int i=0;i<K;i++){
        missinginds[X[i]]=i;
    }
    int ind=0;
    for(int i=0;i<Q*2-1;i++){
        if(s[ind++]=='0'){
            int num=0;
            for(int j=0;j<4;j++){
                num+=(1<<j)*(s[ind++]=='1');
            }
            stk.push_back(1<<num);
            rch.push_back(stk.back());
        }else{
            int comb=stk.back()+stk[stk.size()-2];
            stk.pop_back();stk.back()=comb;
            rch.push_back(comb);
        }
    }
    rch.resize(32);
    for(int i=0;i<K;i++){
        int num=0;
        for(int j=0;j<5;j++){
            num+=(1<<j)*(s[ind++]=='1');
        }
        mreach[X[i]]=num;
    }
    for(int i=0;i<M;i++){
        edges[A[i]].push_back({B[i],i});
        edges[B[i]].push_back({A[i],i});
    }
    for(int qn=0;qn<Q;qn++){
        std::vector<long long> dists(N,1e18);
        std::priority_queue<std::pair<long long,std::pair<int,int>>> dijkstra;
        std::vector<int> parents(N),parentedges(N);
        dijkstra.push({0,{-1,0}});//(-dist, (edgenum,index))
        while(!dijkstra.empty()){
            std::pair<long long,std::pair<int,int>> cur=dijkstra.top();
            dijkstra.pop();
            cur.first=-cur.first;
            int edgenum=cur.second.first;
            int curnode=cur.second.second;
            if(dists[curnode]<=cur.first)continue;
            dists[curnode]=cur.first;
            if(curnode){
                parents[curnode]=A[edgenum]^B[edgenum]^curnode;
                parentedges[curnode]=edgenum;
            }
            for(std::pair<int,int> i:edges[curnode]){
                if(missinginds[i.second]>=0){
                    if(((rch[mreach[i.second]]>>qn)&1)==0)continue;
                }
                dijkstra.push({-(cur.first+std::max(0ll,C[i.second])),{i.second,i.first}});
            }
        }
        std::vector<int> result;
        int loc=T[qn];
        while(loc!=0){
            result.push_back(parentedges[loc]);
            loc=parents[loc];
        }
        std::reverse(result.begin(),result.end());
        answer(result);
    }
}

Compilation message (stderr)

Aoi.cpp: In function 'int {anonymous}::dfs(int)':
Aoi.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<targets.size();i++){
      |                 ~^~~~~~~~~~~~~~~
Aoi.cpp: In function 'std::string aoi(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>)':
Aoi.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j=0;j<nreaches.size();j++){
      |                     ~^~~~~~~~~~~~~~~~

• Subtask 1: 96 / 100