Submission #1326013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326013		Aviansh	Spy 3 (JOI24_spy3)	C++20	0 / 100	72 ms	3676 KiB

Aoi

#include "Aoi.h"

#include <bits/stdc++.h>

using namespace std;

namespace {

int variable_example = 0;

int function_example(int a, int b) { return a + b; }

}  // namespace

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) {
    vector<array<int,2>>g[n];
    for(int i = 0;i<m;i++){
        g[A[i]].push_back({B[i],i});
        g[B[i]].push_back({A[i],i});
    }
    int rev[m];
    fill(rev,rev+m,-1);
    for(int i = 0;i<k;i++){
        rev[X[i]]=i;
    }
    priority_queue<array<long long,2>,vector<array<long long,2>>,greater<array<long long,2>>>pq;
    long long dist[n];
    fill(dist,dist+n,-1);
    dist[0]=0;
    for(array<int,2> e : g[0]){
        pq.push({C[e[1]],e[1]});
    }
    int p[n];
    fill(p,p+n,-1);
    p[0]=-2;
    while(!pq.empty()){
        array<long long,2>e = pq.top();
        pq.pop();
        int node = A[e[1]];
        if(p[node]!=-1){
            node=B[e[1]];
        }
        if(p[node]!=-1){
            continue;
        }
        p[node]=e[1];
        dist[node]=e[0];
        for(array<int,2>ed : g[node]){
            pq.push({dist[node]+C[ed[1]],ed[1]});
        }
    }
    string s = "";
    for(int i = 0;i<q*k;i++){
        s+="0";
    }
    for(int i = 0;i<q;i++){
        int cur = T[i];
        while(cur){
            int edge = p[cur];
            if(rev[edge]!=-1){
                s[i*k+rev[edge]]='1';
            }
            if(cur==A[edge]){
                cur=B[edge];
            }
            else{
                assert(cur==B[edge]);
                cur=A[edge];
            }
        }
    }
    return s;
}

Bitaro

#include "Bitaro.h"

#include <bits/stdc++.h>

using namespace std;

namespace {

int variable_example = 0;

int function_example(int a, int b) { return a + b; }

}  // namespace

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) {
    for(int i : X){
        C[i]=-1;
    }
    vector<array<int,2>>g[n];
    for(int i = 0;i<m;i++){
        g[A[i]].push_back({B[i],i});
        g[B[i]].push_back({A[i],i});
    }
    int rev[m];
    fill(rev,rev+m,-1);
    for(int i = 0;i<k;i++){
        rev[X[i]]=i;
    }
    for(int i = 0;i<q;i++){
        priority_queue<array<long long,2>,vector<array<long long,2>>,greater<array<long long,2>>>pq;
        long long dist[n];
        fill(dist,dist+n,-1);
        dist[0]=0;
        for(array<int,2> e : g[0]){
            pq.push({C[e[1]],e[1]});
        }
        int p[n];
        fill(p,p+n,-1);
        p[0]=-2;
        while(!pq.empty()){
            array<long long,2>e = pq.top();
            pq.pop();
            int node = A[e[1]];
            if(p[node]!=-1){
                node=B[e[1]];
            }
            if(p[node]!=-1){
                continue;
            }
            p[node]=e[1];
            dist[node]=e[0];
            for(array<int,2>ed : g[node]){
                if(rev[ed[1]]!=-1){
                    if(s[i*k+rev[ed[1]]]=='1'){
                        pq.push({dist[node]+0,ed[1]});
                    }
                }
                else{
                    pq.push({dist[node]+C[ed[1]],ed[1]});
                }
            }
        }
        int cur = T[i];
        vector<int>v;
        while(cur){
            int edge = p[cur];
            v.push_back(edge);
            if(cur==A[edge]){
                cur=B[edge];
            }
            else{
                assert(cur==B[edge]);
                cur=A[edge];
            }
        }
        reverse(v.begin(),v.end());
        answer(v);
    }
}

• Subtask 1: 0 / 100