QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706633 | #248. 即时战略 | TheZone | 100 ✓ | 240ms | 33164kb | C++23 | 4.2kb | 2024-11-03 12:43:23 | 2024-11-03 12:43:24 |
Judging History
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);
}
}
/*#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;
access(ii);
}
}*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 3ms
memory: 18320kb
result:
ok # of explore calls = 1
Test #2:
score: 5
Accepted
time: 2ms
memory: 14552kb
result:
ok # of explore calls = 2
Test #3:
score: 5
Accepted
time: 0ms
memory: 18684kb
result:
ok # of explore calls = 18
Test #4:
score: 5
Accepted
time: 2ms
memory: 14428kb
result:
ok # of explore calls = 352
Test #5:
score: 5
Accepted
time: 0ms
memory: 18684kb
result:
ok # of explore calls = 5999
Test #6:
score: 5
Accepted
time: 4ms
memory: 20908kb
result:
ok # of explore calls = 175648
Test #7:
score: 5
Accepted
time: 226ms
memory: 30496kb
result:
ok # of explore calls = 2822874
Test #8:
score: 5
Accepted
time: 3ms
memory: 18560kb
result:
ok # of explore calls = 1006
Test #9:
score: 5
Accepted
time: 0ms
memory: 14676kb
result:
ok # of explore calls = 5008
Test #10:
score: 5
Accepted
time: 4ms
memory: 18988kb
result:
ok # of explore calls = 30010
Test #11:
score: 5
Accepted
time: 34ms
memory: 22428kb
result:
ok # of explore calls = 150007
Test #12:
score: 5
Accepted
time: 58ms
memory: 27704kb
result:
ok # of explore calls = 250010
Test #13:
score: 5
Accepted
time: 84ms
memory: 26732kb
result:
ok # of explore calls = 300010
Test #14:
score: 5
Accepted
time: 2ms
memory: 18608kb
result:
ok # of explore calls = 4547
Test #15:
score: 5
Accepted
time: 4ms
memory: 18672kb
result:
ok # of explore calls = 28328
Test #16:
score: 5
Accepted
time: 15ms
memory: 19500kb
result:
ok # of explore calls = 206280
Test #17:
score: 5
Accepted
time: 105ms
memory: 26856kb
result:
ok # of explore calls = 1198105
Test #18:
score: 5
Accepted
time: 154ms
memory: 27724kb
result:
ok # of explore calls = 1637597
Test #19:
score: 5
Accepted
time: 182ms
memory: 31844kb
result:
ok # of explore calls = 2085284
Test #20:
score: 5
Accepted
time: 240ms
memory: 33164kb
result:
ok # of explore calls = 2542335
Extra Test:
score: 0
Extra Test Passed