oj.uz

Submission #76094

# Submission time Handle Problem Language Result Execution time Memory
76094 2018-09-12T04:26:27 Z thebes Inspection (POI11_ins) C++14
10 / 100
 2336 ms 132096 KB 
#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] = 2* (sm + sum[n]) - a[mx[n].second].first - 1;
        else ans[n] = 2*(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]-sz[v], max(u,b[n].first)+1);
        else dfs2(v, n, N-sz[v], sm+sum[n]-sum[v]-sz[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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 24056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24056 KB Output is correct
2 Correct 22 ms 24224 KB Output is correct
3 Correct 22 ms 24224 KB Output is correct
4 Correct 22 ms 24224 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 26796 KB Output is correct
2 Incorrect 44 ms 27308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 29716 KB Output is correct
2 Incorrect 53 ms 30800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 37972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 88960 KB Output is correct
2 Incorrect 722 ms 104604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2336 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1752 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1920 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -