QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#713901	#7855. 不跳棋	Ryan123	4	264ms	112924kb	C++14	2.1kb	2024-11-05 20:51:08	2024-11-05 20:51:08

Judging History

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

[2024-11-05 20:51:08]
评测

测评结果：4
用时：264ms
内存：112924kb

查看

[2024-11-05 20:51:08]
提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
typedef long long LL;
vector<int> e[N];

int sz[N], all, dis[N][20], p1[N], p2[N], ln[N], dep[N];

vector<int> cnt[N];

bool vis[N];

void get_wc(int x, int fa, int &wc){
    sz[x] = 1; int mx = 0;
    for(int u : e[x])if(u != fa && !vis[u]){
        get_wc(u, x, wc);
        sz[x] += sz[u];
        mx = max(mx, sz[u]);
    }
    mx = max(mx, all - sz[x]);

    if(mx <= all / 2)wc = x;
}

void get_dis(int x, int fa, int D, int rt){
    sz[x] = 1, dis[x][dep[rt]] = D;
    while(D >= ln[rt])
        cnt[rt].push_back(0), ln[rt] ++;
    cnt[rt][D] ++;

    for(int u : e[x]) if(u != fa && !vis[u]){
        get_dis(u, x, D + 1, rt);
        sz[u] += sz[x];
    }
}

int fa[N];
LL cnt2[N];

void modify(int x, int v){
    while(p1[x] < ln[x] && !cnt[x][p1[x]])p1[x] ++;
    p2[x] = max(p2[x], p1[x] + 1);
    while(p2[x] < ln[x] && !cnt[x][p2[x]])p2[x] ++;
    if(p1[x] >= ln[x])return ;
    if(cnt[x][p1[x]] > 1)
         cnt2[2 * p1[x]] += 1ll * cnt[x][p1[x]] * (cnt[x][p1[x]] - 1) / 2 * v;
    else if(p2[x] < ln[x])cnt2[p1[x] + p2[x]] += 1ll * cnt[x][p2[x]] * v;
}

void clac(int x, int D, int p){
    get_wc(x, -1, x);
    fa[x] = p, dep[x] = D;
    vis[x] = 1;
    p1[x] = 0, p2[x] = 1;
    get_dis(x, -1, 0, x);
    modify(x, 1);

    for(int u : e[x]){
        if(!vis[u]){
            all = sz[u];
            clac(u, D + 1, x);
        }
    }
}

int main(){
    int n, tp;
    scanf("%d%d", &n, &tp);
    for(int i = 1; i < n; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
	}
	
	all = n;
    clac(1, 1, 0);

    LL lst;
    int ans1 = 1;
    for(int i = 1; i <= n - 2; i ++){
        LL x;
        scanf("%lld", &x);
        if(tp)x ^= lst;
        int y = x;
        while(y){
            modify(y, -1);
            cnt[y][dis[x][dep[y]]] --;
            modify(y, 1);
            y = fa[y];
        }
        while(!cnt2[ans1])ans1 ++;

        printf("%d %lld\n", ans1, cnt2[ans1]);
        lst = cnt2[ans1];
    }

    return 0;
}

源文件, 语言: C++14

详细

Pretests

Final Tests

Test #1:

score: 0

Wrong Answer

time: 7ms

memory: 40292kb

input:

output:

result:

wrong answer 10th lines differ - expected: '1 83', found: '1 82'

Test #2:

score: 0

Wrong Answer

time: 3ms

memory: 41128kb

input:

output:

result:

wrong answer 16th lines differ - expected: '1 65', found: '1 66'

Test #3:

score: 0

Wrong Answer

time: 3ms

memory: 40764kb

input:

output:

result:

wrong answer 1st lines differ - expected: '1 95', found: '1 97'

Test #4:

score: 0

Runtime Error

input:

output:

result:

Test #5:

score: 0

Runtime Error

input:

output:

result:

Test #6:

score: 0

Runtime Error

input:

output:

result:

Test #7:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #8:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #9:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #10:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #11:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #12:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #13:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #14:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #15:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #16:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #17:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #18:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #19:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #20:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #21:

score: 4

Accepted

time: 264ms

memory: 112924kb

input:

output:

2 124999250001
2 124998750003
2 124998250006
2 124997750010
2 124997250015
2 124996750021
2 124996250028
2 124995750036
2 124995250045
2 124994750055
2 124994250066
2 124993750078
2 124993250091
2 124992750105
2 124992250120
2 124991750136
2 124991250153
2 124990750171
2 124990250190
2 124989750210
...

result:

ok 499998 lines

Test #22:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #23:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #24:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #25:

score: 0

Time Limit Exceeded

input: