QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#711572	#7855. 不跳棋	Liuxizai	48	284ms	52248kb	C++20	3.7kb	2024-11-05 12:08:47	2024-11-05 12:08:48

Judging History

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

[2024-11-05 12:08:48]
评测

测评结果：48
用时：284ms
内存：52248kb

查看

[2024-11-05 12:08:47]
提交

answer

#include <bits/stdc++.h>
#define File(name) freopen(#name".in", "r", stdin); freopen(#name".out", "w", stdout);
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T>
inline T read(){
    T n = 0; int f = 1; char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        n = n * 10 + ch - '0';
        ch = getchar();
    }
    return f * n;
}
template<typename T>
void write(T n){
    if(n < 0) return putchar('-'), write(-n);
    if(n / 10) write(n / 10);
    putchar(n % 10 + '0');
}
void input() {}
template<typename Type, typename... Types>
void input(Type &arg, Types &...args){
    arg = read<Type>();
    input(args...);
}
namespace Main{
    const int N = 200005;
    int n, tp, tot, siz[N], mx[N], rt, mn[N], cnt[N], f[N], dep[N], st[18][N], dfn[N], dfnCnt;
    int ans_d, ans_c;
    bool vis[N], del[N];
    vector<int> g[N];
    inline int dmin(int u, int v) { return dep[u] < dep[v] ? u : v; }
    void calcsiz(int u, int fa){
        siz[u] = 1, mx[u] = 0;
        for(int v: g[u]){
            if(v == fa || vis[v]) continue;
            calcsiz(v, u);
            mx[u] = max(mx[u], siz[v]);
            siz[u] += siz[v];
        }
        mx[u] = max(mx[u], tot - siz[u]);
        if(mx[u] < mx[rt]) rt = u;
    }
    void solve(int u){
        vis[u] = true;
        for(int v: g[u]){
            if(vis[v]) continue;
            tot = siz[v], rt = 0;
            calcsiz(v, u);
            calcsiz(rt, 0);
            f[rt] = u;
            solve(rt);
        }
    }
    void dfs(int u, int fa){
        st[0][dfn[u] = ++dfnCnt] = fa;
        dep[u] = dep[fa] + 1;
        for(int v: g[u]){
            if(v == fa) continue;
            dfs(v, u);
        }
    }
    int lca(int u, int v){
        if(u == v) return u;
        if(dfn[u] > dfn[v]) swap(u, v);
        int lg = log2(dfn[v] - dfn[u]);
        return dmin(st[lg][dfn[u] + 1], st[lg][dfn[v] - (1 << lg) + 1]);
    }
    int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
    void add(int u){
        int cur = u;
        while(cur){
            int d0 = dis(u, cur), d = mn[cur] + dis(u, cur);
            if(d < ans_d) ans_d = d, ans_c = cnt[cur];
            else if(d == ans_d) ans_c += cnt[cur];
            if(d0 < mn[cur]) mn[cur] = d0, cnt[cur] = 1;
            else if(d0 == mn[cur]) cnt[cur]++;
            cur = f[cur];
        }
    }
    void Main(){
        input(n, tp);
        for(int i = 1, u, v; i < n; i++){
            input(u, v);
            g[u].push_back(v), g[v].push_back(u);
        }
        dfs(1, 0);
        for(int i = 1; i < 18; i++){
            for(int j = 1; j + (1 << i) - i <= n; j++){
                st[i][j] = dmin(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
        mx[0] = 1e9;
        tot = n, rt = 0;
        calcsiz(1, 0);
        calcsiz(rt, 0);
        solve(rt);
        vector<int> vec;
        for(int i = 0, u; i < n - 2; i++) input(u), vec.push_back(u), del[u] = true;
        reverse(vec.begin(), vec.end());
        for(int i = 1; i <= n; i++) mn[i] = 1e9;
        ans_d = 1e9;
        for(int i = 1; i <= n; i++) if(!del[i]) add(i);
        vector<pair<int, int>> ans;
        for(int u: vec) ans.emplace_back(ans_d, ans_c), add(u);
        reverse(ans.begin(), ans.end());
        for(auto [d, c]: ans) write(d), putchar(' '), write(c), puts("");
        return;
    }
} // namespace Main
int main(){
#ifdef Liuxizai
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif // Liuxizai
    Main::Main();
    return 0;
}

源文件, 语言: C++20

详细

Pretests

Final Tests

Test #1:

score: 4

Accepted

time: 0ms

memory: 11836kb

input:

output:

result:

ok 98 lines

Test #2:

score: 4

Accepted

time: 2ms

memory: 11896kb

input:

output:

result:

ok 98 lines

Test #3:

score: 4

Accepted

time: 2ms

memory: 9940kb

input:

output:

result:

ok 98 lines

Test #4:

score: 4

Accepted

time: 3ms

memory: 13996kb

input:

output:

result:

ok 998 lines

Test #5:

score: 4

Accepted

time: 2ms

memory: 13948kb

input:

output:

result:

ok 998 lines

Test #6:

score: 4

Accepted

time: 0ms

memory: 16080kb

input:

output:

result:

ok 998 lines

Test #7:

score: 4

Accepted

time: 211ms

memory: 36612kb

input:

output:

result:

ok 199998 lines

Test #8:

score: 4

Accepted

time: 209ms

memory: 36412kb

input:

output:

result:

ok 199998 lines

Test #9:

score: 4

Accepted

time: 228ms

memory: 36768kb

input:

output:

result:

ok 199998 lines

Test #10:

score: 4

Accepted

time: 284ms

memory: 52040kb

input:

output:

result:

ok 199998 lines

Test #11:

score: 4

Accepted

time: 265ms

memory: 39124kb

input:

output:

result:

ok 199998 lines

Test #12:

score: 4

Accepted

time: 258ms

memory: 39248kb

input:

output:

result:

ok 199998 lines

Test #13:

score: 0

Runtime Error

input:

output:

result:

Test #14:

score: 0

Runtime Error

input:

output:

result:

Test #15:

score: 0

Wrong Answer

time: 254ms

memory: 52248kb

input:

output:

result:

wrong answer 1st lines differ - expected: '1 199997', found: '0 28180495'

Test #16:

score: 0

Runtime Error

input:

output:

result:

Test #17:

score: 0

Runtime Error

input:

output:

result:

Test #18:

score: 0

Wrong Answer

time: 260ms

memory: 36648kb

input:

output:

-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
-3 1
...

result:

wrong answer 1st lines differ - expected: '1 199997', found: '-3 1'

Test #19:

score: 0

Runtime Error

input:

output:

result:

Test #20:

score: 0

Runtime Error

input:

output:

result:

Test #21:

score: 0

Runtime Error

input:

output:

result:

Test #22:

score: 0

Runtime Error

input:

output:

result:

Test #23:

score: 0

Runtime Error

input:

output:

result:

Test #24:

score: 0

Runtime Error

input:

output:

result:

Test #25:

score: 0

Runtime Error

input: