oj.uz

Submission #584256

# Submission time Handle Problem Language Result Execution time Memory
584256 2022-06-27T05:58:39 Z 조영욱(#8377) Meetings 2 (JOI21_meetings2) C++17
20 / 100
 144 ms 30768 KB 
#include <bits/stdc++.h>
using namespace std;

int sz[200001];
vector<int> adj[200001];
typedef pair<int,int> P;
P val[200001];
int ret[100001];
int table[100001][17];
int dep[100001];

void dfs(int v,int prev) {
    sz[v]=1;
    table[v][0]=prev;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        dep[nt]=dep[v]+1;
        dfs(nt,v);
        sz[v]+=sz[nt];
    }
}

int getcent(int v,int prev,int half) {
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        if (sz[nt]>half) {
            return getcent(nt,v,half);
        }
    }
    return v;
}

int lca(int a,int b) {
    if (dep[a]<dep[b]) {
        swap(a,b);
    }
    int diff=dep[a]-dep[b];
    for(int i=0;diff;i++) {
        if (diff&1) {
            a=table[a][i];
        }
        diff/=2;
    }
if (a==b) return a;
    for(int i=16;i>=0;i--) {
        if (table[a][i]!=0&&table[a][i]!=table[b][i]) {
            a=table[a][i];
            b=table[b][i];
        }
    }
    return table[a][0];
}

int dist(int a,int b) {
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    int c=getcent(1,0,n/2);
    dep[c]=0;
    dfs(c,0);
    for(int j=1;j<17;j++) {
        for(int i=1;i<=n;i++) {
            if (table[i][j-1]!=0) {
                table[i][j]=table[table[i][j-1]][j-1];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        val[i].first=n;
if (i==c) {
int mx=0;
        for(int j=0;j<adj[i].size();j++) {
            mx=max(mx,sz[adj[i][j]]);
        }
val[i].first=n-mx;
}
else {
val[i].first=sz[i];
}
//printf("%d\n",val[i].first);
        val[i].second=i;
    }
    sort(val+1,val+n+1);
    reverse(val+1,val+n+1);
    int ind=1;
    int one=0;
    int two=0;
    int mx=-1;
    for(int i=n;i>0;i--) {
        while (ind<=n&&val[ind].first==i) {
            int now=val[ind].second;
            if (one==0) {
                one=now;
                two=now;
                mx=0;
                continue;
            }
            if (dist(one,now)>mx) {
                mx=dist(one,now);
                two=now;
            }
            else if (dist(now,two)>mx) {
                mx=dist(now,two);
                one=now;
            }
ind++;
        }
if (i<=n/2)
        ret[i]=mx+1;
    }
    for(int i=1;i<=n;i++) {
        printf("%d\n",i%2==0?ret[i/2]:1);
    }
    return 0;
}

Compilation message

meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
meetings2.cpp: In function 'int getcent(int, int, int)':
meetings2.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int j=0;j<adj[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
meetings2.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
meetings2.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4932 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4964 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4932 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4964 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 5 ms 5460 KB Output is correct
23 Correct 5 ms 5400 KB Output is correct
24 Correct 5 ms 5460 KB Output is correct
25 Correct 7 ms 5460 KB Output is correct
26 Correct 5 ms 5496 KB Output is correct
27 Correct 6 ms 5460 KB Output is correct
28 Correct 7 ms 5484 KB Output is correct
29 Correct 5 ms 5460 KB Output is correct
30 Correct 5 ms 5460 KB Output is correct
31 Correct 5 ms 5484 KB Output is correct
32 Correct 5 ms 5588 KB Output is correct
33 Correct 5 ms 5588 KB Output is correct
34 Correct 5 ms 5460 KB Output is correct
35 Correct 4 ms 5460 KB Output is correct
36 Correct 5 ms 5460 KB Output is correct
37 Correct 5 ms 5460 KB Output is correct
38 Correct 5 ms 5588 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4932 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4964 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 5 ms 5460 KB Output is correct
23 Correct 5 ms 5400 KB Output is correct
24 Correct 5 ms 5460 KB Output is correct
25 Correct 7 ms 5460 KB Output is correct
26 Correct 5 ms 5496 KB Output is correct
27 Correct 6 ms 5460 KB Output is correct
28 Correct 7 ms 5484 KB Output is correct
29 Correct 5 ms 5460 KB Output is correct
30 Correct 5 ms 5460 KB Output is correct
31 Correct 5 ms 5484 KB Output is correct
32 Correct 5 ms 5588 KB Output is correct
33 Correct 5 ms 5588 KB Output is correct
34 Correct 5 ms 5460 KB Output is correct
35 Correct 4 ms 5460 KB Output is correct
36 Correct 5 ms 5460 KB Output is correct
37 Correct 5 ms 5460 KB Output is correct
38 Correct 5 ms 5588 KB Output is correct
39 Runtime error 144 ms 30768 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -