QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#59108#248. 即时战略hhblw100 ✓500ms31732kbC++232.8kb2022-10-27 22:27:362022-10-27 22:27:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-27 22:27:59]
  • 评测
  • 测评结果:100
  • 用时:500ms
  • 内存:31732kb
  • [2022-10-27 22:27:36]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
#include "rts.h"
using namespace std;
typedef long long ll;
#define N 300002
int id[N], fa[N], son[N][2], mn[N], mx[N], ansfa[N];
bool vis[N];
inline bool isroot(int x) {
    return x != son[fa[x]][0] && x != son[fa[x]][1];
}
inline bool getlr(int x) {
    return son[fa[x]][1] == x;
}
inline void pushup(int x) {
    mn[x] = son[x][0] ? mn[son[x][0]] : x;
    mx[x] = son[x][1] ? mx[son[x][1]] : x;
}
inline void rota(int x) {
    int f = fa[x], ff = fa[f], w = getlr(x);

    if (!isroot(f))
        son[ff][getlr(f)] = x;

    son[f][w] = son[x][w ^ 1];
    fa[son[x][w ^ 1]] = f;
    son[x][w ^ 1] = f;
    fa[x] = ff, fa[f] = x;
    pushup(f), pushup(x);
}
inline void splay(int x) {
    for (register int f = fa[x]; !isroot(x); f = fa[x]) {
        if (!isroot(f))
            rota(getlr(f) == getlr(x) ? f : x);

        rota(x);
    }
}
inline int fdrt(int x) {
    while (!isroot(x))
        x = fa[x];

    return x;
}
inline void access(int x) {
    int t = 0;

    while (x) {
        splay(x);
        son[x][1] = t;
        pushup(x);
        t = x, x = fa[x];
    }
}
void play(int n, int T, int dataType) {
    srand(time(NULL));
    int cnt = 0;

    for (int i = 2; i <= n; i++)
        id[i] = i;

    random_shuffle(id + 2, id + 1 + n);
    vis[1] = 1;

    if (dataType == 3) {
        int le = 1, ri = 1;

        for (int i = 2; i <= n; i++)
            if (!vis[id[i]]) {
                int x = id[i];
                int te = explore(le, x);

                if (vis[te]) {
                    te = explore(ri, x);
                    vis[te] = 1;

                    while (te != x)
                        te = explore(te, x), vis[te] = 1;

                    ri = x;
                } else {
                    vis[te] = 1;

                    while (te != x)
                        te = explore(te, x), vis[te] = 1;

                    le = x;
                }
            }

        return;
    }

    for (int i = 1; i <= n; i++)
        mn[i] = mx[i] = i;

    for (int i = 2; i <= n; i++)
        if (!vis[id[i]]) {
            int x = fdrt(1), tt = 1, ii = id[i];

            while (x ^ ii) {
                int te = explore(x, ii);
                cnt++;

                if (!vis[te]) {
                    fa[te] = x;
                    vis[te] = 1;
                    tt = te;
                }

                if (son[x][1] && te == mn[son[x][1]])
                    x = son[x][1];
                else if (son[x][0] && te == mx[son[x][0]])
                    x = son[x][0];
                else
                    x = fdrt(te);
            }

            access(ii);
        }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 3ms
memory: 4096kb

result:

ok # of explore calls = 1

Test #2:

score: 5
Accepted
time: 1ms
memory: 4188kb

result:

ok # of explore calls = 2

Test #3:

score: 5
Accepted
time: 2ms
memory: 4120kb

result:

ok # of explore calls = 14

Test #4:

score: 5
Accepted
time: 1ms
memory: 4116kb

result:

ok # of explore calls = 322

Test #5:

score: 5
Accepted
time: 3ms
memory: 4064kb

result:

ok # of explore calls = 5783

Test #6:

score: 5
Accepted
time: 9ms
memory: 5888kb

result:

ok # of explore calls = 176459

Test #7:

score: 5
Accepted
time: 427ms
memory: 26744kb

result:

ok # of explore calls = 2826332

Test #8:

score: 5
Accepted
time: 3ms
memory: 4144kb

result:

ok # of explore calls = 1003

Test #9:

score: 5
Accepted
time: 5ms
memory: 4424kb

result:

ok # of explore calls = 5003

Test #10:

score: 5
Accepted
time: 8ms
memory: 6308kb

result:

ok # of explore calls = 30006

Test #11:

score: 5
Accepted
time: 41ms
memory: 15140kb

result:

ok # of explore calls = 150006

Test #12:

score: 5
Accepted
time: 84ms
memory: 22336kb

result:

ok # of explore calls = 250011

Test #13:

score: 5
Accepted
time: 140ms
memory: 26172kb

result:

ok # of explore calls = 300011

Test #14:

score: 5
Accepted
time: 4ms
memory: 4156kb

result:

ok # of explore calls = 4559

Test #15:

score: 5
Accepted
time: 6ms
memory: 4548kb

result:

ok # of explore calls = 28218

Test #16:

score: 5
Accepted
time: 27ms
memory: 6868kb

result:

ok # of explore calls = 206480

Test #17:

score: 5
Accepted
time: 137ms
memory: 17936kb

result:

ok # of explore calls = 1198114

Test #18:

score: 5
Accepted
time: 256ms
memory: 22556kb

result:

ok # of explore calls = 1642100

Test #19:

score: 5
Accepted
time: 370ms
memory: 27172kb

result:

ok # of explore calls = 2092098

Test #20:

score: 5
Accepted
time: 500ms
memory: 31732kb

result:

ok # of explore calls = 2543403

Extra Test:

score: 0
Extra Test Passed