제출 #1198393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198393		biank	Spy 3 (JOI24_spy3)	C++20	0 / 100	49 ms	3380 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 < 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 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: 0 / 100