Submission #1198395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198395		biank	Spy 3 (JOI24_spy3)	C++20	8 / 100	62 ms	3660 KiB

Aoi

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

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;

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) {
        sort(all(X));
        /*vector<vector<tuple<int, ll, int>>> adj(N);
        for (int i = 0; i < M; i++) {
            adj[A[i]].emplace_back(B[i], C[i], i);
            adj[B[i]].emplace_back(A[i], C[i], i);
        }
        priority_queue<pair<ll, int>> pq;
        vector<ll> dist(N, ll(1e18));
        pq.emplace(-(dist[0] = 0), 0);
        vector<int> par(N, -1);
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop(); d *= -1;
            if (d != dist[u]) continue;
            for (auto [v, w, i] : adj[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    par[v] = i;
                    pq.emplace(-dist[v], v);
                }
            }
        }*/
        string ans = "";
        for (int i = 0; i < K; i++) {
            for (int bit = 0; bit < 40; bit++) {
                ans += '0' + bool(C[X[i]] >> bit & 1);
            }
        }
        /*for (int i = 0; i < Q; i++) {
            int u = T[i];
            set<int> used;
            while (u != 0) {
                used.insert(par[u]);
                u ^= A[par[u]] ^ B[par[u]];
            }
            for (int j = 0; j < K; j++) {
                ans += '0' + used.count(j);
            }
        }*/
        return ans;
}

Bitaro

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

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;


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) {
        sort(all(X));
        int idx = 0;
        for (int i = 0; i < K; i++) {
            C[X[i]] = 0;
            for (int bit = 0; bit < 40; bit++) {
                if (s[idx] == '1') C[X[i]] += 1LL << bit;
                idx++;
            }
        }
        for (int p = 0; p < Q; p++) {
            //int j = 0;
            vector<vector<tuple<int, ll, int>>> adj(N);
            for (int i = 0; i < M; i++) {
                ll w = C[i];
                /*if (j < K && X[j] == i) {
                    if (s[idx] == '0') w = ll(1e18);
                    else w = 0;
                    idx++, j++;
                }*/
                adj[A[i]].emplace_back(B[i], w, i);
                adj[B[i]].emplace_back(A[i], w, i);
            }
            priority_queue<pair<ll, int>> pq;
            vector<ll> dist(N, ll(1e18));
            pq.emplace(-(dist[0] = 0), 0);
            vector<int> par(N, -1);
            while (!pq.empty()) {
                auto [d, u] = pq.top();
                pq.pop(); d *= -1;
                if (d != dist[u]) continue;
                for (auto [v, w, i] : adj[u]) {
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        par[v] = i;
                        pq.emplace(-dist[v], v);
                    }
                }
            }
            int u = T[p];
            vector<int> path;
            while (u != 0) {
                path.push_back(par[u]);
                u ^= A[par[u]] ^ B[par[u]];
            }
            reverse(all(path));
            answer(path);
        }
}

• Subtask 1: 8 / 100