QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#707923#8642. Spy 3hhoppitree0 25ms8812kbC++178.7kb2024-11-03 18:12:592024-11-03 18:13:00

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 18:13:00]
  • 评测
  • 测评结果:0
  • 用时:25ms
  • 内存:8812kb
  • [2024-11-03 18:12:59]
  • 提交

Aoi

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

using namespace std;

vector<int> operator * (vector<int> x, int y) {
    if (x.empty()) return {};
    vector<int> tres(x.size());
    for (int i = 0; i < (int)x.size(); ++i) {
        tres[i] += x[i] * y;
        if (i + 1 != (int)x.size()) {
            tres[i + 1] += tres[i] >> 10;
            tres[i] &= 1023;
        }
    }
    while (tres.back() >= 1024) {
        tres.push_back(tres.back() >> 10);
        tres[tres.size() - 2] &= 1023;
    }
    return tres;
}

vector<int> operator + (vector<int> x, int y) {
    if (!y) return x;
    if (x.empty()) {
        x = {0};
    }
    x[0] += y;
    int r = 0;
    while (r < (int)x.size() && x[r] >= 1024) {
        x[r] -= 1024;
        if (r == (int)x.size() - 1) x.push_back(0);
        ++x[r + 1];
    }
    return x;
}

string tr(vector<int> arr) {
    string res;
    for (int i = (int)arr.size() - 1; ~i; --i) {
        for (int j = 9; ~j; --j) {
            res += (char)(((arr[i] >> j) & 1) + '0');
        }
    }
    while (!res.empty() && res[0] == '0') {
        res = res.substr(1);
    }
    return res;
}

namespace Aoi {
    const int N = 1e4 + 5;

    vector< pair<int, long long> > G[N];
    long long dis[N];
    int pre[N];
    vector<int> T[N];
    int dep[N], clk[N];

    void dfs(int x) {
        for (auto v : T[x]) {
            dep[v] = dep[x] + 1, dfs(v), clk[x] = min(clk[x], clk[v]);
        }
    }
    
    int visit[N];

    void mark(int x) {
        while (x) {
            visit[x] = 1;
            x = pre[x];
        }
    }

    int getLst(int x) {
        while (x) {
            if (visit[x]) return x;
            x = pre[x];
        }
        return 0;
    }

    map< pair<int, int>, int> spe;

    int getId(int x) {
        while (x) {
            if (spe.count({x, pre[x]})) {
                return spe[{x, pre[x]}] + 1;
            }
            x = pre[x];
        }
        return 0;
    }

    string calc(vector< pair<int, int> > o) {
        vector<int> res;
        for (int i = (int)o.size() - 1; ~i; --i) {
            res = res * o[i].first + o[i].second;
        }
        return tr(res);
    }

    string aoi(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o) {
        for (int i = 0; i < m; ++i) {
            G[ox[i]].push_back({oy[i], oz[i]});
            G[oy[i]].push_back({ox[i], oz[i]});
        }
        for (int i = 1; i < n; ++i) {
            dis[i] = 1e18;
        }
        priority_queue< pair<long long, int> > pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            long long D = -pq.top().first;
            int x = pq.top().second;
            pq.pop();
            if (D != dis[x]) continue;
            for (auto [v, w] : G[x]) {
                long long nD = D + w;
                if (nD < dis[v] || (nD == dis[v] && x < pre[v])) {
                    if (nD != dis[v]) pq.push({-nD, v});
                    dis[v] = nD, pre[v] = x;
                }
            }
        }
        for (int i = 0; i < n; ++i) clk[i] = q;
        for (int i = 0; i < q; ++i) {
            clk[qr[i]] = min(clk[qr[i]], i);
        }
        for (int i = 1; i < n; ++i) {
            T[pre[i]].push_back(i);
        }
        dfs(0);
        vector< pair<int, int> > res;
        for (int i = 0; i < k; ++i) {
            if (dep[ox[o[i]]] > dep[oy[o[i]]]) swap(ox[o[i]], oy[o[i]]);
            res.push_back({q + 1, (pre[oy[o[i]]] == ox[o[i]] ? clk[oy[o[i]]] : q)});
            spe[{ox[o[i]], oy[o[i]]}] = spe[{oy[o[i]], ox[o[i]]}] = i;
        }
        mark(qr[0]);
        for (int i = 1; i < q; ++i) {
            res.push_back({k + 1, getId(getLst(qr[i]))});
            mark(qr[i]);
        }
        string ret = calc(res);
        assert((int)ret.size() <= 1350);
        return ret;
    }
}

string aoi(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o) {
    return Aoi::aoi(n, m, q, k, ox, oy, oz, qr, o);
}

Bitaro

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

using namespace std;

vector<int> operator / (vector<int> x, int y) {
    vector<int> tres(x.size());
    int now = 0;
    for (int i = (int)x.size() - 1; ~i; --i) { 
        now = (now << 10) + x[i];
        tres[i] = now / y;
        now %= y;
    }
    while (!tres.empty() && !tres.back()) {
        tres.pop_back();
    }
    return tres;
}

int operator % (vector<int> x, int y) {
    vector<int> tres(x.size());
    int now = 0;
    for (int i = (int)x.size() - 1; ~i; --i) { 
        now = (now << 10) + x[i];
        tres[i] = now / y;
        now %= y;
    }
    return now;
}

vector<int> parse(string S) {
    while (S.size() % 10) S = "0" + S;
    vector<int> res(S.size() / 10);
    for (int i = 0; i < (int)S.size(); i += 10) {
        for (int j = 0; j < 10; ++j) {
            res[(int)S.size() / 10 - 1 - i / 10] += (S[i + j] - '0') << (9 - j);
        }
    }
    return res;
}

namespace Bitaro {
    const int N = 1e4 + 5;

    vector<int> apd[N];
    int pre[N], det[N], dep[N], usd[N << 1];
    vector< tuple<int, int, long long> > E;
    long long dis[N];
    vector< pair<int, int> > ts;
    vector< pair<int, long long> > G[N];

    vector<int> process(int n, vector<int> imp, int id) {
        for (int i = 0; i < n; ++i) {
            G[i].clear();
            dis[i] = (i == 0 ? 0 : 1e18), pre[i] = 0;
        }
        for (auto [x, y, z] : E) {
            G[x].push_back({y, z});
            G[y].push_back({x, z});
        }
        for (auto x : imp) {
            G[ts[x].first].push_back({ts[x].second, 0});
            G[ts[x].second].push_back({ts[x].first, 0});
        }
        priority_queue< pair<long long, int> > pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            long long D = -pq.top().first;
            int x = pq.top().second;
            pq.pop();
            if (D != dis[x]) continue;
            for (auto [v, w] : G[x]) {
                long long nD = D + w;
                if (nD < dis[v] || (nD == dis[v] && x < pre[v])) {
                    if (nD != dis[v]) pq.push({-nD, v});
                    dis[v] = nD, pre[v] = x;
                }
            }
        }
        vector<int> path = {id};
        int now = id;
        while (now) {
            path.push_back(pre[now]);
            now = pre[now];
        }
        reverse(path.begin(), path.end());
        for (int i = 1; i < (int)path.size(); ++i) {
            det[path[i]] = path[i - 1];
            dep[path[i]] = dep[path[i - 1]] + 1;
        }
        return path;
    }

    void bitaro(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o, string S) {
        vector<int> val = parse(S);
        map< pair<int, int>, int> zM;
        for (int i = 0; i < k; ++i) {
            int cl = val % (q + 1);
            val = val / (q + 1);
            apd[cl].push_back(i);
            zM[{ox[o[i]], oy[o[i]]}] = zM[{oy[o[i]], ox[o[i]]}] = i;
        }
        map< pair<int, int>, int> M;
        for (int i = 0; i < m; ++i) {
            M[{ox[i], oy[i]}] = M[{oy[i], ox[i]}] = i;
        }
        for (int i = 0; i < k; ++i) {
            usd[o[i]] = 1;
            ts.push_back({ox[o[i]], oy[o[i]]});
        }
        for (int i = 0; i < m; ++i) {
            if (!usd[i]) E.push_back({ox[i], oy[i], oz[i]});
        }
        for (int i = 0; i < q; ++i) {
            vector<int> imp;
            if (i) {
                int id = val % (k + 1);
                val = val / (k + 1);
                if (id) {
                    --id;
                    if (dep[ox[o[id]]] < dep[oy[o[id]]]) {
                        swap(ox[o[id]], oy[o[id]]);
                    }
                    id = ox[o[id]];
                    while (id) {
                        if (usd[M[{id, det[id]}]]) {
                            imp.push_back(zM[{id, det[id]}]);
                        }
                        id = det[id];
                    }
                }
            }
            for (auto x : apd[i]) {
                imp.push_back(x);
            }
            vector<int> res = process(n, imp, qr[i]);
            vector<int> ids;
            for (int j = 0; j + 1 < (int)res.size(); ++j) {
                ids.push_back(M[{res[j], res[j + 1]}]);
            }
            answer(ids);
        }
    }
}

void bitaro(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o, string S) {
    Bitaro::bitaro(n, m, q, k, ox, oy, oz, qr, o, S);
}

詳細信息

Test #1:

score: 100
Accepted
time: 25ms
memory: 8812kb

Manager to Aoi

200 19900
13 70 985302938314
120 174 18964037101
18 153 170196070829
45 129 323777973024
62 198 689223413645
88 133 457404464825
19 57 803409835578
22 187 662331177910
18 31 529437059733
161 182 637731822589
109 131 32831735773
109 191 875742441191
43 78 135479410688
56 60 19000632823
44 143 6823771...

Aoi to Manager

A11010111100100001101010000011010100001011000001101000010000100101000010111110001101001010110100011110111110100000000010010111010000110101001011101001000110100100001001001100001100110110011110110100010100010101110101101000011111010001000100100110100101010111101101001111001011101111111000100100101110...

Manager to Bitaro

200 19900
13 70 985302938314
120 174 18964037101
18 153 170196070829
45 129 323777973024
62 198 689223413645
88 133 457404464825
19 57 803409835578
22 187 662331177910
18 31 529437059733
161 182 637731822589
109 131 32831735773
109 191 875742441191
43 78 135479410688
56 60 19000632823
44 143 6823771...

Bitaro to Manager

4
17135 3534 4830 14466
1
11921
2
17135 9906
4
17135 3534 18777 907
6
18033 13659 9145 14255 10379 11567
7
11921 7585 5782 2139 15549 19315 13987
2
17135 13815
5
17135 13815 8201 7265 15719
4
17135 3534 4830 9175
4
11921 7585 5782 8018
2
18033 13659
4
11921 7585 10922 14444
5
468 273 10532 11483 845...

Manager to Checker

1.00

result:

points 1.0

Test #2:

score: 100
Accepted
time: 1ms
memory: 4556kb

Manager to Aoi

6 7
0 5 839719370667
2 4 244076065937
1 5 337346113825
2 3 716558559511
1 4 837188452057
0 3 661778933008
1 3 678360389380
5
2 3 1 5 4
7
4 2 0 6 1 5 3

Aoi to Manager

A111111000110101101100111010001F

Manager to Bitaro

6 7
0 5 -1
2 4 -1
1 5 -1
2 3 -1
1 4 -1
0 3 -1
1 3 -1
5
2 3 1 5 4
7
4 2 0 6 1 5 3
A111111000110101101100111010001F

Bitaro to Manager

2
5 3
1
5
2
0 2
1
0
3
5 3 1
F

Manager to Checker

1.00

result:

points 1.0

Test #3:

score: 0
Instance #1 Time Limit Exceeded

Manager to Aoi

10000 19480
2933 9484 1000000000000
2567 9405 1000000000000
5263 6064 1000000000000
1453 8911 1000000000000
2445 8695 1000000000000
5686 7074 1000000000000
5031 5441 1000000000000
253 5144 1000000000000
8087 8704 1000000000000
263 3499 1000000000000
5200 8741 1000000000000
5764 8908 1000000000000
20...

Aoi to Manager

A11100111101111010010100000101011100000010010110110001001110011110110000110111110011101110110000100011011011001011010101101001010110010000011100000100011011100100000111110011011101101011011000010111101100110100100110101111110000001000111010010101010010010001100000101011100101001100000101000011110011...

Manager to Bitaro

10000 19480
2933 9484 1000000000000
2567 9405 1000000000000
5263 6064 1000000000000
1453 8911 1000000000000
2445 8695 1000000000000
5686 7074 1000000000000
5031 5441 1000000000000
253 5144 1000000000000
8087 8704 1000000000000
263 3499 1000000000000
5200 8741 1000000000000
5764 8908 1000000000000
20...

Bitaro to Manager


Manager to Checker

0.00

result: