oj.uz

Submission #995118

# Submission time Handle Problem Language Result Execution time Memory
995118 2024-06-08T13:21:04 Z prvocislo Spy 3 (JOI24_spy3) C++17
38 / 100
 933 ms 39476 KB 
#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;
}

#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 86 ms 8628 KB Partially correct
2 Correct 0 ms 784 KB Output is correct
3 Partially correct 799 ms 11108 KB Partially correct
4 Partially correct 783 ms 18560 KB Partially correct
5 Partially correct 74 ms 7316 KB Partially correct
6 Partially correct 554 ms 9384 KB Partially correct
7 Partially correct 642 ms 10020 KB Partially correct
8 Partially correct 322 ms 8436 KB Partially correct
9 Partially correct 645 ms 17672 KB Partially correct
10 Partially correct 124 ms 10128 KB Partially correct
11 Partially correct 219 ms 8028 KB Partially correct
12 Correct 444 ms 8960 KB Output is correct
13 Partially correct 242 ms 8152 KB Partially correct
14 Correct 103 ms 7528 KB Output is correct
15 Correct 234 ms 8092 KB Output is correct
16 Correct 63 ms 9200 KB Output is correct
17 Partially correct 933 ms 30988 KB Partially correct
18 Partially correct 712 ms 29376 KB Partially correct
19 Partially correct 86 ms 9128 KB Partially correct
20 Partially correct 67 ms 9124 KB Partially correct
21 Partially correct 84 ms 9256 KB Partially correct
22 Partially correct 78 ms 8636 KB Partially correct
23 Partially correct 58 ms 8708 KB Partially correct
24 Partially correct 73 ms 8480 KB Partially correct
25 Partially correct 86 ms 19088 KB Partially correct
26 Partially correct 90 ms 19068 KB Partially correct
27 Correct 1 ms 832 KB Output is correct
28 Correct 193 ms 8124 KB Output is correct
29 Partially correct 72 ms 16356 KB Partially correct
30 Correct 182 ms 8520 KB Output is correct
31 Partially correct 120 ms 8220 KB Partially correct
32 Partially correct 192 ms 8588 KB Partially correct
33 Correct 78 ms 7528 KB Output is correct
34 Correct 80 ms 8104 KB Output is correct
35 Correct 203 ms 8572 KB Output is correct
36 Partially correct 622 ms 10836 KB Partially correct
37 Partially correct 54 ms 32056 KB Partially correct
38 Partially correct 147 ms 39476 KB Partially correct
39 Partially correct 90 ms 24548 KB Partially correct
40 Partially correct 20 ms 15124 KB Partially correct
41 Partially correct 370 ms 9620 KB Partially correct
42 Partially correct 81 ms 9160 KB Partially correct
43 Correct 97 ms 8876 KB Output is correct
44 Partially correct 34 ms 8628 KB Partially correct
45 Partially correct 53 ms 16864 KB Partially correct
46 Partially correct 70 ms 20396 KB Partially correct
47 Correct 29 ms 5528 KB Output is correct
48 Correct 0 ms 776 KB Output is correct
49 Correct 1 ms 776 KB Output is correct
50 Partially correct 143 ms 8664 KB Partially correct
51 Partially correct 4 ms 1288 KB Partially correct
52 Correct 0 ms 784 KB Output is correct
53 Partially correct 92 ms 8912 KB Partially correct
54 Partially correct 55 ms 5748 KB Partially correct
55 Partially correct 67 ms 6264 KB Partially correct
56 Partially correct 76 ms 8732 KB Partially correct
57 Partially correct 107 ms 8872 KB Partially correct
58 Partially correct 72 ms 6584 KB Partially correct
59 Partially correct 99 ms 8764 KB Partially correct
60 Partially correct 106 ms 8812 KB Partially correct
61 Partially correct 112 ms 8888 KB Partially correct
62 Partially correct 95 ms 7864 KB Partially correct
63 Correct 112 ms 8932 KB Output is correct
64 Partially correct 30 ms 7204 KB Partially correct
65 Partially correct 44 ms 5628 KB Partially correct
66 Partially correct 60 ms 9052 KB Partially correct
67 Partially correct 45 ms 5604 KB Partially correct
68 Partially correct 54 ms 8880 KB Partially correct
69 Correct 1 ms 784 KB Output is correct
70 Correct 0 ms 784 KB Output is correct
71 Partially correct 2 ms 776 KB Partially correct
72 Partially correct 18 ms 4116 KB Partially correct
73 Partially correct 34 ms 4892 KB Partially correct
74 Partially correct 36 ms 4836 KB Partially correct
75 Partially correct 23 ms 4632 KB Partially correct
76 Correct 1 ms 784 KB Output is correct
77 Correct 76 ms 7316 KB Output is correct
78 Partially correct 113 ms 7460 KB Partially correct
79 Correct 98 ms 7404 KB Output is correct
80 Correct 0 ms 776 KB Output is correct
81 Partially correct 112 ms 7536 KB Partially correct
82 Partially correct 157 ms 7732 KB Partially correct
83 Partially correct 132 ms 7496 KB Partially correct