Submission #1335442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335442		anteknne	Spy 3 (JOI24_spy3)	C++20	0 / 100	11 ms	2084 KiB

Aoi

#include "Aoi.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

namespace{
    const int MAXN = 10 * 1000 + 17;
    const int MAXM = 20 * 1000 + 17;
    const int MAXK = 300 + 17;
    const ll INF = ll(1000 * 1000 * 1000) * ll(1000 * 1000 * 1000);
    ll cena[MAXM];
    vector<pii> graf[MAXN];
    pii poprz[MAXN];
    ll odl[MAXN];
    bool jest[MAXK];
    priority_queue<pair<ll, int>> pq;
    int n;
}

void djikstra () {
    for (int i = 0; i < n; i ++) {
        odl[i] = INF;
    }
    odl[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        //cout << v << ":\n";
        int v = pq.top().nd;
        ll d = -pq.top().st;
        pq.pop();
        if (d > odl[v]) {
            continue;
        }

        for (auto x : graf[v]) {
            if (odl[v] + cena[x.nd] < odl[x.st]) {
                odl[x.st] = odl[v] + cena[x.nd];
                poprz[x.st] = {v, x.nd};
                pq.push({-odl[x.st], x.st});
            }
        }
    }
}

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) {
    string s = "";
    n = N;

    for (int i = 0; i < M; i ++) {
        cena[i] = C[i];
        graf[A[i]].pb({B[i], i});
        graf[B[i]].pb({A[i], i});
    }

    djikstra();

    for (int i = 0; i < Q; i ++) {
        int v = T[i];
        for (int j = 0; j < K; j ++) {
            jest[j] = 0;
        }
        while (v != 0) {
            for (int j = 0; j < K; j ++) {
                if (X[j] == poprz[v].nd) {
                    jest[j] = 1;
                }
            }
            v = poprz[v].st;
        }
        for (int j = 0; j < K; j ++) {
            if (jest[j]) {
                s += "1";
            } else {
                s += "0";
            }
        }
    }
    //cout << s << "\n";
    return s;
}

Bitaro

#include "Bitaro.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

namespace {
    const int MAXN = 10 * 1000 + 17;
    const int MAXM = 20 * 1000 + 17;
    const int MAXK = 300 + 17;
    const ll INF = ll(1000 * 1000 * 1000) * ll(1000 * 1000 * 1000);
    ll cena2[MAXM];
    vector<pii> graf2[MAXN];
    pii poprz2[MAXN];
    ll odl2[MAXN];
    priority_queue<pair<ll, int>> pq2;
    vector<int> wyn;
    int n2;

void djikstra2 () {
    for (int i = 0; i < n2; i ++) {
        odl2[i] = INF;
    }
    odl2[0] = 0;
    pq2.push({0, 0});
    while (!pq2.empty()) {
        //cout << v << ":\n";
        int v = pq2.top().nd;
        ll d = -pq2.top().st;
        pq2.pop();
        if (d > odl2[v]) {
            continue;
        }

        for (auto x : graf2[v]) {
            if (odl2[v] + cena2[x.nd] < odl2[x.st]) {
                odl2[x.st] = odl2[v] + cena2[x.nd];
                poprz2[x.st] = {v, x.nd};
                pq2.push({-odl2[x.st], x.st});
            }
        }
    }
}
}

void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B, vector<ll> C, vector<int> T, vector<int> X, string s){
    n2 = N;
    for (int i = 0; i < M; i ++) {
        cena2[i] = C[i];
        graf2[A[i]].pb({B[i], i});
        graf2[B[i]].pb({A[i], i});
    }

    for (int i = 0; i < Q; i ++) {
        for (int j = 0; j < K; j ++) {
            if (s[i * K + j] == '1') {
                cena2[X[j]] = 0;
            } else {
                cena2[X[j]] = 1;
            }
        }
        djikstra2();

        int v = T[i];
        while (v != 0) {
            wyn.pb(poprz2[v].nd);
            v = poprz2[v].st;
        }
        reverse(wyn.begin(), wyn.end());
        answer(wyn);

        wyn.clear();

    }
}

• Subtask 1: 0 / 100