Submission #995118

#	Time	Username	Problem	Language	Result	Execution time	Memory
995118		prvocislo	Spy 3 (JOI24_spy3)	C++17	38 / 100	933 ms	39476 KiB

Aoi

#include "Aoi.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

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) 
{
    const ll inf = 1e18 + 5;
    vector<ll> d(n, inf);
    vector<int>p(n, -1);
    vector<vector<pair<int, ll> > > g(n);
    for (int i = 0; i < m; i++) g[a[i]].push_back({ b[i], c[i] }), g[b[i]].push_back({ a[i], c[i] });
    set<pair<ll, pair<int, int> > > pq;
    pq.insert({ 0, {0, -1} });
    while (!pq.empty())
    {
        ll di = pq.begin()->first;
        int u = pq.begin()->second.first;
        int pi = pq.begin()->second.second;
        pq.erase(pq.begin());
        if (d[u] != inf) continue;
        d[u] = di;
        p[u] = pi;
        for (pair<int, ll> v : g[u]) if (d[v.first] == inf)
        {
            pq.insert({ d[u] + v.second, { v.first, u } });
        }
    }
    map<pair<int, int>, int> id;
    vector<pair<int, int> > anc;
    string s;
    for (int i = 0; i < k; i++)
    {
        if (d[a[x[i]]] < d[b[x[i]]]) s.push_back('0'), anc.push_back({ a[x[i]], b[x[i]] }), id[{ a[x[i]], b[x[i]] }] = i;
        else s.push_back('1'), anc.push_back({ b[x[i]], a[x[i]] }), id[{ b[x[i]], a[x[i]] }] = i;
    }
    for (int i = 0; i < q; i++) anc.push_back({ t[i], t[i] });
    for (int i = 0; i < anc.size(); i++)
    {
        int st = anc[i].first;
        int x = 0;
        while (st != 0)
        {
            if (id.count({ p[st], st }))
            {
                x = id[{ p[st], st }] + 1;
                break;
            }
            st = p[st];
        }
        for (int b = 0; b < 9; b++) s.push_back((x & (1 << b)) ? '1' : '0');
    }
    return s;
}

Bitaro

#include "Bitaro.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

namespace {
    const ll inf = 1e18 + 5;
    int n, m, q, k;
    vector<int> a, b, t, x;
    vector<ll> c;
    string s;
    vector<vector<pair<int, ll> > > g;
    map<pair<int, int>, int> idk, id;
    void solve(int id, vector<int> &vr) // vrcholy, potom to zmenime na hrany
    {
        int pv = 0;
        for (int j = 0; j < 9; j++) if (s[k + id * 9 + j] == '1') pv += (1 << j);
        int st = (pv ? b[x[pv - 1]] : 0);
        vector<ll> d(n, inf);
        vector<int>p(n, -1);
        set<pair<ll, pair<int, int> > > pq;
        pq.insert({ 0, {st, -1} });
        while (!pq.empty())
        {
            ll di = pq.begin()->first;
            int u = pq.begin()->second.first;
            int pi = pq.begin()->second.second;
            pq.erase(pq.begin());
            if (d[u] != inf) continue;
            d[u] = di;
            p[u] = pi;
            for (pair<int, ll> v : g[u]) if (d[v.first] == inf && v.second != inf)
            {
                pq.insert({ d[u] + v.second, { v.first, u } });
            }
        }
        int en = (id >= k ? t[id - k] : a[x[id]]);
        while (en != st)
        {
            vr.push_back(en);
            en = p[en];
        }
        vr.push_back(st);
        if (pv) solve(pv - 1, vr);
    }
}

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) 
{
    n = N, m = M, q = Q, k = K, a = A, b = B, c = C, t = T, x = X, s = S;
    for (int i = 0; i < k; i++)
    {
        if (s[i] == '1') swap(a[x[i]], b[x[i]]);
        idk[{a[x[i]], b[x[i]]}] = i;
        c[x[i]] = inf;
    }
    g.assign(n, {});
    for (int i = 0; i < m; i++) id[{a[i], b[i]}] = id[{b[i], a[i]}] = i, g[a[i]].push_back({ b[i], c[i] }), g[b[i]].push_back({ a[i], c[i] });
    for (int i = 0; i < q; i++)
    {
        vector<int> vr;
        solve(k + i, vr);
        vector<int> e;
        for (int j = 0; j + 1 < vr.size(); j++) e.push_back(id[{vr[j], vr[j + 1]}]);
        reverse(e.begin(), e.end());
        answer(e);
    }
}

Compilation message (stderr)

Aoi.cpp: In function 'std::string aoi(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>)':
Aoi.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < anc.size(); i++)
      |                     ~~^~~~~~~~~~~~

Bitaro.cpp: In function 'void bitaro(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::string)':
Bitaro.cpp:80:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int j = 0; j + 1 < vr.size(); j++) e.push_back(id[{vr[j], vr[j + 1]}]);
      |                         ~~~~~~^~~~~~~~~~~

• Subtask 1: 38 / 100