답안 #90876 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90876	2018-12-25T05:03:49 Z	mirbek01	Hard route (IZhO17_road)	C++11	100 / 100	1229 ms	76668 KB

road

# include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 2;

int n, up[N];
vector <int> g[N], roots;
pair <long long, long long> ans, dp[N];

void dfs1(int v, int pr = 0){
      dp[v] = {0, 1};
      for(int to : g[v]){
            if(to == pr)
                  continue;
            dfs1(to, v);
            if(dp[to].first + 1 > dp[v].first){
                  dp[to].first ++;
                  dp[v] = dp[to];
                  dp[to].first --;
            } else if(dp[to].first + 1 == dp[v].first){
                  dp[v].second += dp[to].second;
            }
      }
}

void dfs2(int v, int pr = 0){
      pair <int, int> mx[2];
      mx[0].first = mx[1].first = -1;
      if(up[v] > mx[0].first)
            mx[0] = {up[v], pr};
      for(int to : g[v]){
            if(to == pr)
                  continue;
            if(dp[to].first + 1 > mx[0].first){
                  mx[1] = mx[0];
                  mx[0] = {dp[to].first + 1, to};
            } else if(dp[to].first + 1 > mx[1].first)
                  mx[1] = {dp[to].first + 1, to};
      }
      for(int to : g[v]){
            if(to == pr)
                  continue;
            if(mx[0].second != to){
                  up[to] = mx[0].first + 1;
            } else {
                  up[to] = mx[1].first + 1;
            }
            dfs2(to, v);
      }
}

void update(int &mx1, int &mx2, int &mx3, int val){
      if(val > mx1){
            mx3 = mx2;
            mx2 = mx1;
            mx1 = val;
      } else if(val > mx2){
            mx3 = mx2;
            mx2 = val;
      } else if(val > mx3){
            mx3 = val;
      }
}

void dfs3(int v, int pr = 0){
      int mx1 = -1, mx2 = -1, mx3 = -1;
      if(pr){
            update(mx1, mx2, mx3, up[v]);
      }
      for(int to : g[v]){
            if(to == pr)
                  continue;
            dfs3(to, v);
            update(mx1, mx2, mx3, dp[to].first + 1);
      }
      if(mx3 != -1){
            long long ret = (mx2 + mx3)  * 1ll * mx1;
            if(ret > ans.first){
                  ans.first = ret;
                  roots.clear();
            }
            if(ret == ans.first)
                  roots.push_back(v);
      }
}

void dfs(int root){
      vector < pair <long long, long long> > vec;
      dfs1(root);
      for(int to : g[root]){
            dp[to].first ++;
            vec.push_back(dp[to]);
      }
      if(vec.size() < 3)
            return ;
      sort(vec.rbegin(), vec.rend());
      while(vec.size() > 3 && vec.back().first < vec[2].first)
            vec.pop_back();
      int sum = 0;
      for(int i = 0; i < vec.size(); i ++){
            if(vec[i].first == vec[2].first)
                  sum += vec[i].second;
      }
      for(int i = 0; i < vec.size(); i ++){
            if(vec[i].first == vec[2].first)
                  sum -= vec[i].second;
            if(vec[i].first == vec[1].first)
                  ans.second += vec[i].second * 1ll * sum;
      }
}

int main(){
      scanf("%d", &n);

      for(int i = 1; i < n; i ++){
            int u, v;
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
      }

      dfs1(1);
      dfs2(1);
      dfs3(1);

      for(int i = 0; i < roots.size(); i ++){
            dfs(roots[i]);
      }

      if(ans.first == 0)
            ans.second = 1;

      cout << ans.first << " " << ans.second << endl;
}

Compilation message

road.cpp: In function 'void dfs(int)':
road.cpp:101:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < vec.size(); i ++){
                      ~~^~~~~~~~~~~~
road.cpp:105:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < vec.size(); i ++){
                      ~~^~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:127:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < roots.size(); i ++){
                      ~~^~~~~~~~~~~~~~
road.cpp:114:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
road.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	12152 KB	Output is correct
2	Correct	10 ms	12152 KB	Output is correct
3	Correct	10 ms	12208 KB	Output is correct
4	Correct	31 ms	12212 KB	Output is correct
5	Correct	10 ms	12268 KB	Output is correct
6	Correct	10 ms	12268 KB	Output is correct
7	Correct	12 ms	12268 KB	Output is correct
8	Correct	10 ms	12268 KB	Output is correct
9	Correct	10 ms	12268 KB	Output is correct
10	Correct	10 ms	12268 KB	Output is correct
11	Correct	12 ms	12308 KB	Output is correct
12	Correct	10 ms	12308 KB	Output is correct
13	Correct	12 ms	12308 KB	Output is correct
14	Correct	10 ms	12308 KB	Output is correct
15	Correct	10 ms	12368 KB	Output is correct
16	Correct	10 ms	12368 KB	Output is correct
17	Correct	10 ms	12368 KB	Output is correct
18	Correct	10 ms	12368 KB	Output is correct
19	Correct	10 ms	12368 KB	Output is correct
20	Correct	10 ms	12368 KB	Output is correct
21	Correct	10 ms	12368 KB	Output is correct
22	Correct	10 ms	12368 KB	Output is correct
23	Correct	10 ms	12368 KB	Output is correct
24	Correct	10 ms	12368 KB	Output is correct

Subtask #2
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	12152 KB	Output is correct
2	Correct	10 ms	12152 KB	Output is correct
3	Correct	10 ms	12208 KB	Output is correct
4	Correct	31 ms	12212 KB	Output is correct
5	Correct	10 ms	12268 KB	Output is correct
6	Correct	10 ms	12268 KB	Output is correct
7	Correct	12 ms	12268 KB	Output is correct
8	Correct	10 ms	12268 KB	Output is correct
9	Correct	10 ms	12268 KB	Output is correct
10	Correct	10 ms	12268 KB	Output is correct
11	Correct	12 ms	12308 KB	Output is correct
12	Correct	10 ms	12308 KB	Output is correct
13	Correct	12 ms	12308 KB	Output is correct
14	Correct	10 ms	12308 KB	Output is correct
15	Correct	10 ms	12368 KB	Output is correct
16	Correct	10 ms	12368 KB	Output is correct
17	Correct	10 ms	12368 KB	Output is correct
18	Correct	10 ms	12368 KB	Output is correct
19	Correct	10 ms	12368 KB	Output is correct
20	Correct	10 ms	12368 KB	Output is correct
21	Correct	10 ms	12368 KB	Output is correct
22	Correct	10 ms	12368 KB	Output is correct
23	Correct	10 ms	12368 KB	Output is correct
24	Correct	10 ms	12368 KB	Output is correct
25	Correct	13 ms	12772 KB	Output is correct
26	Correct	14 ms	12780 KB	Output is correct
27	Correct	14 ms	12780 KB	Output is correct
28	Correct	15 ms	12780 KB	Output is correct
29	Correct	15 ms	12780 KB	Output is correct
30	Correct	13 ms	12800 KB	Output is correct
31	Correct	12 ms	12800 KB	Output is correct
32	Correct	15 ms	12800 KB	Output is correct
33	Correct	14 ms	12800 KB	Output is correct
34	Correct	14 ms	12800 KB	Output is correct
35	Correct	14 ms	12800 KB	Output is correct
36	Correct	14 ms	12800 KB	Output is correct
37	Correct	15 ms	12800 KB	Output is correct
38	Correct	14 ms	12924 KB	Output is correct
39	Correct	14 ms	12924 KB	Output is correct
40	Correct	15 ms	12924 KB	Output is correct
41	Correct	13 ms	12924 KB	Output is correct
42	Correct	13 ms	12924 KB	Output is correct
43	Correct	15 ms	12924 KB	Output is correct
44	Correct	15 ms	12924 KB	Output is correct
45	Correct	14 ms	12924 KB	Output is correct
46	Correct	14 ms	12924 KB	Output is correct
47	Correct	14 ms	12924 KB	Output is correct
48	Correct	14 ms	12924 KB	Output is correct

Subtask #3
48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	12152 KB	Output is correct
2	Correct	10 ms	12152 KB	Output is correct
3	Correct	10 ms	12208 KB	Output is correct
4	Correct	31 ms	12212 KB	Output is correct
5	Correct	10 ms	12268 KB	Output is correct
6	Correct	10 ms	12268 KB	Output is correct
7	Correct	12 ms	12268 KB	Output is correct
8	Correct	10 ms	12268 KB	Output is correct
9	Correct	10 ms	12268 KB	Output is correct
10	Correct	10 ms	12268 KB	Output is correct
11	Correct	12 ms	12308 KB	Output is correct
12	Correct	10 ms	12308 KB	Output is correct
13	Correct	12 ms	12308 KB	Output is correct
14	Correct	10 ms	12308 KB	Output is correct
15	Correct	10 ms	12368 KB	Output is correct
16	Correct	10 ms	12368 KB	Output is correct
17	Correct	10 ms	12368 KB	Output is correct
18	Correct	10 ms	12368 KB	Output is correct
19	Correct	10 ms	12368 KB	Output is correct
20	Correct	10 ms	12368 KB	Output is correct
21	Correct	10 ms	12368 KB	Output is correct
22	Correct	10 ms	12368 KB	Output is correct
23	Correct	10 ms	12368 KB	Output is correct
24	Correct	10 ms	12368 KB	Output is correct
25	Correct	13 ms	12772 KB	Output is correct
26	Correct	14 ms	12780 KB	Output is correct
27	Correct	14 ms	12780 KB	Output is correct
28	Correct	15 ms	12780 KB	Output is correct
29	Correct	15 ms	12780 KB	Output is correct
30	Correct	13 ms	12800 KB	Output is correct
31	Correct	12 ms	12800 KB	Output is correct
32	Correct	15 ms	12800 KB	Output is correct
33	Correct	14 ms	12800 KB	Output is correct
34	Correct	14 ms	12800 KB	Output is correct
35	Correct	14 ms	12800 KB	Output is correct
36	Correct	14 ms	12800 KB	Output is correct
37	Correct	15 ms	12800 KB	Output is correct
38	Correct	14 ms	12924 KB	Output is correct
39	Correct	14 ms	12924 KB	Output is correct
40	Correct	15 ms	12924 KB	Output is correct
41	Correct	13 ms	12924 KB	Output is correct
42	Correct	13 ms	12924 KB	Output is correct
43	Correct	15 ms	12924 KB	Output is correct
44	Correct	15 ms	12924 KB	Output is correct
45	Correct	14 ms	12924 KB	Output is correct
46	Correct	14 ms	12924 KB	Output is correct
47	Correct	14 ms	12924 KB	Output is correct
48	Correct	14 ms	12924 KB	Output is correct
49	Correct	882 ms	53760 KB	Output is correct
50	Correct	858 ms	55336 KB	Output is correct
51	Correct	856 ms	57724 KB	Output is correct
52	Correct	834 ms	57724 KB	Output is correct
53	Correct	595 ms	57724 KB	Output is correct
54	Correct	778 ms	57724 KB	Output is correct
55	Correct	631 ms	57724 KB	Output is correct
56	Correct	694 ms	57724 KB	Output is correct
57	Correct	675 ms	59268 KB	Output is correct
58	Correct	754 ms	59268 KB	Output is correct
59	Correct	622 ms	59268 KB	Output is correct
60	Correct	639 ms	59268 KB	Output is correct
61	Correct	811 ms	76668 KB	Output is correct
62	Correct	1039 ms	76668 KB	Output is correct
63	Correct	1221 ms	76668 KB	Output is correct
64	Correct	1229 ms	76668 KB	Output is correct
65	Correct	1075 ms	76668 KB	Output is correct
66	Correct	1140 ms	76668 KB	Output is correct
67	Correct	1061 ms	76668 KB	Output is correct
68	Correct	932 ms	76668 KB	Output is correct
69	Correct	896 ms	76668 KB	Output is correct
70	Correct	913 ms	76668 KB	Output is correct
71	Correct	858 ms	76668 KB	Output is correct
72	Correct	905 ms	76668 KB	Output is correct
73	Correct	913 ms	76668 KB	Output is correct
74	Correct	872 ms	76668 KB	Output is correct
75	Correct	870 ms	76668 KB	Output is correct
76	Correct	942 ms	76668 KB	Output is correct
77	Correct	849 ms	76668 KB	Output is correct
78	Correct	507 ms	76668 KB	Output is correct

답안 #90876

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 33.0 / 33.0

Subtask #3 48.0 / 48.0

Subtask #1
19.0 / 19.0

Subtask #2
33.0 / 33.0

Subtask #3
48.0 / 48.0