Submission #990824

#	Time	Username	Problem	Language	Result	Execution time	Memory
990824		Pacybwoah	Spy 3 (JOI24_spy3)	C++17	100 / 100	83 ms	6596 KiB

Aoi

#include "Aoi.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
namespace {
    vector<vector<pair<pair<int, ll>, int>>> graph;
    int n, m, q, k;
}
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) {
    n = N, m = M, q = Q, k = K;
    graph.resize(n);
    for(int i = 0; i < m; i++){
        graph[A[i]].emplace_back(make_pair(B[i], C[i]), i);
        graph[B[i]].emplace_back(make_pair(A[i], C[i]), i);
    }
    priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
    vector<ll> dist(n, 1e18);
    dist[0] = 0;
    vector<pair<int, int>> par(n);
    pq.emplace(0, make_pair(0, 0));
    while(!pq.empty()){
        auto [d, tmp] = pq.top();
        auto [node, eidd] = tmp;
        pq.pop();
        if(dist[node] < d) continue;
        if(node != 0){
            par[node] = make_pair((A[eidd] == node ? B[eidd] : A[eidd]), eidd);
        }
        for(auto &[x, eid]: graph[node]){
            if(dist[x.first] > d + x.second){
                dist[x.first] = d + x.second;
                pq.emplace(dist[x.first], make_pair(x.first, eid));
            }
        }
    }
    vector<bool> isq(n), isk(m);
    for(auto x: T) isq[x] = 1;
    for(auto x: X) isk[x] = 1;
    vector<int> qtag(n, -1), ktag(m, -1);
    int now;
    for(int i = q - 1; i >= 0; i--){
        now = T[i];
        while(now != 0){
            auto &[p, eid] = par[now];
            if(isk[eid]) ktag[eid] = i;
            now = p;
        }
    }
    for(int i = 0; i < q; i++){
        now = T[i];
        while(now != 0){
            auto &[p, eid] = par[now];
            if(isk[eid]){
                if(ktag[eid] < i && ktag[eid] != -1){
                    qtag[i] = eid;
                    break;
                }
            }
            now = p;
        }
    }
    vector<int> kpos(m);
    for(int i = 0; i < k; i++) kpos[X[i]] = i;
    string ans;
    for(int s = 0; s < k; s += 6){
        int e = min(s + 5, k - 1);
        ll enc = 0, base = 1;
        for(int i = s; i <= e; i++){
            enc += base * (ktag[X[i]] + 1);
            base *= 17;
        }
        for(int i = 0; i < 25; i++){
            if(enc & (1 << i)){
                ans += '1';
            }
            else ans += '0';
        }
    }
    for(int i = 1; i < q; i++){
        int enc;
        if(qtag[i] == -1) enc = 0;
        else enc = kpos[qtag[i]] + 1;
        for(int j = 0; j < 9; j++){
            if(enc & (1 << j)){
                ans += '1';
            }
            else ans += '0';
        }
    }
    return ans;
}

// g++ -std=gnu++20 -O2 -o grader joisc24_d1C_grader.cpp joisc24_d1C_Aoi.cpp joisc24_d1C_Bitaro.cpp

Bitaro

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<string>
#include "Bitaro.h"
using namespace std;
typedef long long ll;
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) {
    int n = N, m = M, q = Q, k = K;
    vector<int> ktag(k), qtag(q);
    int snow = 0;
    //cout << s << "\n";
    for(int st = 0; st < k; st += 6){
        int e = min(k, st + 6);
        int enc = 0;
        for(int i = snow; i < snow + 25; i++){
            if(s[i] == '1') enc += (1 << (i - snow));
        }
        snow += 25;
        for(int i = st; i < e; i++){
            ktag[i] = enc % 17 - 1;
            enc /= 17;
            //cout << i << " " << ktag[i] << "\n";
        }
    }
    for(int i = 1; i < q; i++){
        for(int j = snow; j < snow + 9; j++){
            if(s[j] == '1') qtag[i] += (1 << (j - snow));
        }
        snow += 9;
        qtag[i]--;
        //cout << i << " " << qtag[i] << "\n";
    }
    //for(auto x: qtag) cout << x << " ";
    //cout << "\n";
    //for(auto x: ktag) cout << x << " ";
    //cout << "\n";
    vector<bool> used(k), isk(m), isq(n);
    vector<int> kpos(m);
    for(int i = 0; i < k; i++) isk[X[i]] = 1;
    for(int i = 0; i < q; i++) isq[T[i]] = 1;
    for(int i = 0; i < k; i++) kpos[X[i]] = i;
    vector<vector<pair<pair<int, ll>, int>>> graph;
    auto set_graph = [&](){
        vector<vector<pair<pair<int, ll>, int>>>().swap(graph);
        graph.resize(n);
        for(int i = 0; i < m; i++){
            if(!isk[i]){
                graph[A[i]].emplace_back(make_pair(B[i], C[i]), i);
                graph[B[i]].emplace_back(make_pair(A[i], C[i]), i);
            }
        }
        for(int i = 0; i < k; i++){
            if(used[i]){
                graph[A[X[i]]].emplace_back(make_pair(B[X[i]], 1), X[i]);
                graph[B[X[i]]].emplace_back(make_pair(A[X[i]], 1), X[i]);
            }
        }
    };
    vector<int> head(k, -1);
    auto dijk = [&](int nowq){
        priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
        vector<ll> dist(n, 1e18);
        dist[0] = 0;
        pq.emplace(0, make_pair(0, 0));
        vector<pair<int, int>> par(n);
        while(!pq.empty()){
            auto [d, tmp] = pq.top();
            auto [node, eidd] = tmp;
            pq.pop();
            if(dist[node] < d) continue;
            if(node != 0){
                par[node] = make_pair((A[eidd] == node ? B[eidd] : A[eidd]), eidd);
            }
            for(auto &[x, eid]: graph[node]){
                if(dist[x.first] > d + x.second){
                    dist[x.first] = d + x.second;
                    pq.emplace(dist[x.first], make_pair(x.first, eid));
                }
            }
        }
        vector<int> ans;
        int lst = -1;
        while(nowq != 0){
            auto &[p, eid] = par[nowq];
            if(isk[eid]){
                if(lst != -1){
                    head[lst] = kpos[eid];
                }
                lst = kpos[eid];
            }
            nowq = p;
            ans.push_back(eid);
        }
        reverse(ans.begin(), ans.end());
        //for(auto x: ans) cout << x << "\n";
        //cout << "\n";
        answer(ans);
    };
    for(int i = 0; i < q; i++){
        fill(used.begin(), used.end(), 0);
        for(int j = 0; j < k; j++){
            if(ktag[j] == i) used[j] = 1;
        }
        if(i != 0){
            while(qtag[i] >= 0){
                used[qtag[i]] = 1;
                qtag[i] = head[qtag[i]];
            }
        }
        set_graph();
        dijk(T[i]);
    }
}
// g++ -std=gnu++20 -O2 -o grader joisc24_d1C_grader.cpp joisc24_d1C_Aoi.cpp joisc24_d1C_Bitaro.cpp

• Subtask 1: 100 / 100