Submission #76091

#	Time	Username	Problem	Language	Result	Execution time	Memory
76091		thebes	Untitled (POI11_ins)	C++14	0 / 100	2390 ms	132096 KiB

Main

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

#define int long long
const int MN = 1e6+6;
int N, i, x, y, sz[MN], sum[MN], ans[MN];
vector<int> adj[MN];
pair<int,int> a[MN], b[MN], mx[MN];

void dfs1(int n, int p){
    sz[n] = 1;
    for(auto v : adj[n]){
        if(v == p) continue;
        dfs1(v, n);
        pair<int,int> w={a[v].first+1,v};
        if(w.first > a[n].first) b[n]=a[n], a[n]=w;
        else if(w.first > b[n].first) b[n] = w;
        sz[n] += sz[v];
        if(sz[v] > mx[n].first)
            mx[n] = {sz[v], v};
        sum[n] += sum[v]+sz[v];
    }
}

void dfs2(int n, int p, int Sz, int sm, int u){
    sm += Sz;
    if(max(Sz,mx[n].first) <= (N-1)/2+((N-1)%2)){
        if(N%2==0&&mx[n].first==(N-1)/2+((N-1)%2))
            ans[n] = sm + sum[n] - a[mx[n].second].first - 1;
        else ans[n] = sm + sum[n] - max(u, a[n].first);
    }
    else ans[n] = -1;
    for(auto v : adj[n]){
        if(v == p) continue;
        if(v == a[n].second)
            dfs2(v, n, N-sz[v], sm+sum[n]-sum[v], max(u,b[n].first)+1);
        else dfs2(v, n, N-sz[v], sm+sum[n]-sum[v], max(u,a[n].first)+1);
    }
}

signed main(){
    for(scanf("%lld",&N),i=1;i<N;i++){
        scanf("%lld%lld",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 0, 0, 0, 0);
    for(i=1;i<=N;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

Compilation message (stderr)

ins.cpp: In function 'int main()':
ins.cpp:42:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%lld",&N),i=1;i<N;i++){
         ~~~~~~~~~~~~~~~~^~~~
ins.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10