답안 #90874 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90874	2018-12-25T04:52:36 Z	mirbek01	Hard route (IZhO17_road)	C++17	52 / 100	1245 ms	263096 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	11 ms	12024 KB	Output is correct
2	Correct	10 ms	12152 KB	Output is correct
3	Correct	10 ms	12264 KB	Output is correct
4	Correct	10 ms	12264 KB	Output is correct
5	Correct	10 ms	12264 KB	Output is correct
6	Correct	10 ms	12336 KB	Output is correct
7	Correct	10 ms	12336 KB	Output is correct
8	Correct	10 ms	12336 KB	Output is correct
9	Correct	10 ms	12368 KB	Output is correct
10	Correct	10 ms	12416 KB	Output is correct
11	Correct	10 ms	12416 KB	Output is correct
12	Correct	10 ms	12416 KB	Output is correct
13	Correct	10 ms	12416 KB	Output is correct
14	Correct	10 ms	12416 KB	Output is correct
15	Correct	15 ms	12444 KB	Output is correct
16	Correct	10 ms	12444 KB	Output is correct
17	Correct	10 ms	12444 KB	Output is correct
18	Correct	11 ms	12444 KB	Output is correct
19	Correct	12 ms	12444 KB	Output is correct
20	Correct	12 ms	12460 KB	Output is correct
21	Correct	10 ms	12460 KB	Output is correct
22	Correct	12 ms	12520 KB	Output is correct
23	Correct	10 ms	12520 KB	Output is correct
24	Correct	10 ms	12520 KB	Output is correct

Subtask #2
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	12024 KB	Output is correct
2	Correct	10 ms	12152 KB	Output is correct
3	Correct	10 ms	12264 KB	Output is correct
4	Correct	10 ms	12264 KB	Output is correct
5	Correct	10 ms	12264 KB	Output is correct
6	Correct	10 ms	12336 KB	Output is correct
7	Correct	10 ms	12336 KB	Output is correct
8	Correct	10 ms	12336 KB	Output is correct
9	Correct	10 ms	12368 KB	Output is correct
10	Correct	10 ms	12416 KB	Output is correct
11	Correct	10 ms	12416 KB	Output is correct
12	Correct	10 ms	12416 KB	Output is correct
13	Correct	10 ms	12416 KB	Output is correct
14	Correct	10 ms	12416 KB	Output is correct
15	Correct	15 ms	12444 KB	Output is correct
16	Correct	10 ms	12444 KB	Output is correct
17	Correct	10 ms	12444 KB	Output is correct
18	Correct	11 ms	12444 KB	Output is correct
19	Correct	12 ms	12444 KB	Output is correct
20	Correct	12 ms	12460 KB	Output is correct
21	Correct	10 ms	12460 KB	Output is correct
22	Correct	12 ms	12520 KB	Output is correct
23	Correct	10 ms	12520 KB	Output is correct
24	Correct	10 ms	12520 KB	Output is correct
25	Correct	13 ms	12928 KB	Output is correct
26	Correct	15 ms	12980 KB	Output is correct
27	Correct	15 ms	13176 KB	Output is correct
28	Correct	15 ms	13176 KB	Output is correct
29	Correct	15 ms	13340 KB	Output is correct
30	Correct	13 ms	13340 KB	Output is correct
31	Correct	14 ms	13364 KB	Output is correct
32	Correct	15 ms	13416 KB	Output is correct
33	Correct	13 ms	13468 KB	Output is correct
34	Correct	15 ms	13520 KB	Output is correct
35	Correct	14 ms	13732 KB	Output is correct
36	Correct	13 ms	13732 KB	Output is correct
37	Correct	15 ms	13732 KB	Output is correct
38	Correct	15 ms	14016 KB	Output is correct
39	Correct	14 ms	14016 KB	Output is correct
40	Correct	16 ms	14016 KB	Output is correct
41	Correct	15 ms	14016 KB	Output is correct
42	Correct	15 ms	14016 KB	Output is correct
43	Correct	15 ms	14016 KB	Output is correct
44	Correct	15 ms	14016 KB	Output is correct
45	Correct	14 ms	14016 KB	Output is correct
46	Correct	14 ms	14016 KB	Output is correct
47	Correct	15 ms	14216 KB	Output is correct
48	Correct	14 ms	14520 KB	Output is correct

Subtask #3
0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	12024 KB	Output is correct
2	Correct	10 ms	12152 KB	Output is correct
3	Correct	10 ms	12264 KB	Output is correct
4	Correct	10 ms	12264 KB	Output is correct
5	Correct	10 ms	12264 KB	Output is correct
6	Correct	10 ms	12336 KB	Output is correct
7	Correct	10 ms	12336 KB	Output is correct
8	Correct	10 ms	12336 KB	Output is correct
9	Correct	10 ms	12368 KB	Output is correct
10	Correct	10 ms	12416 KB	Output is correct
11	Correct	10 ms	12416 KB	Output is correct
12	Correct	10 ms	12416 KB	Output is correct
13	Correct	10 ms	12416 KB	Output is correct
14	Correct	10 ms	12416 KB	Output is correct
15	Correct	15 ms	12444 KB	Output is correct
16	Correct	10 ms	12444 KB	Output is correct
17	Correct	10 ms	12444 KB	Output is correct
18	Correct	11 ms	12444 KB	Output is correct
19	Correct	12 ms	12444 KB	Output is correct
20	Correct	12 ms	12460 KB	Output is correct
21	Correct	10 ms	12460 KB	Output is correct
22	Correct	12 ms	12520 KB	Output is correct
23	Correct	10 ms	12520 KB	Output is correct
24	Correct	10 ms	12520 KB	Output is correct
25	Correct	13 ms	12928 KB	Output is correct
26	Correct	15 ms	12980 KB	Output is correct
27	Correct	15 ms	13176 KB	Output is correct
28	Correct	15 ms	13176 KB	Output is correct
29	Correct	15 ms	13340 KB	Output is correct
30	Correct	13 ms	13340 KB	Output is correct
31	Correct	14 ms	13364 KB	Output is correct
32	Correct	15 ms	13416 KB	Output is correct
33	Correct	13 ms	13468 KB	Output is correct
34	Correct	15 ms	13520 KB	Output is correct
35	Correct	14 ms	13732 KB	Output is correct
36	Correct	13 ms	13732 KB	Output is correct
37	Correct	15 ms	13732 KB	Output is correct
38	Correct	15 ms	14016 KB	Output is correct
39	Correct	14 ms	14016 KB	Output is correct
40	Correct	16 ms	14016 KB	Output is correct
41	Correct	15 ms	14016 KB	Output is correct
42	Correct	15 ms	14016 KB	Output is correct
43	Correct	15 ms	14016 KB	Output is correct
44	Correct	15 ms	14016 KB	Output is correct
45	Correct	14 ms	14016 KB	Output is correct
46	Correct	14 ms	14016 KB	Output is correct
47	Correct	15 ms	14216 KB	Output is correct
48	Correct	14 ms	14520 KB	Output is correct
49	Correct	850 ms	62452 KB	Output is correct
50	Correct	846 ms	71240 KB	Output is correct
51	Correct	859 ms	80528 KB	Output is correct
52	Correct	830 ms	83912 KB	Output is correct
53	Correct	634 ms	90808 KB	Output is correct
54	Correct	719 ms	100620 KB	Output is correct
55	Correct	875 ms	101344 KB	Output is correct
56	Correct	731 ms	111156 KB	Output is correct
57	Correct	860 ms	124764 KB	Output is correct
58	Correct	877 ms	128772 KB	Output is correct
59	Correct	849 ms	135952 KB	Output is correct
60	Correct	818 ms	141588 KB	Output is correct
61	Correct	1047 ms	170856 KB	Output is correct
62	Correct	1050 ms	170964 KB	Output is correct
63	Correct	1208 ms	170964 KB	Output is correct
64	Correct	1245 ms	170964 KB	Output is correct
65	Correct	951 ms	170964 KB	Output is correct
66	Correct	968 ms	170964 KB	Output is correct
67	Correct	1190 ms	175312 KB	Output is correct
68	Correct	1169 ms	182068 KB	Output is correct
69	Correct	865 ms	189192 KB	Output is correct
70	Correct	1119 ms	196180 KB	Output is correct
71	Correct	1123 ms	203164 KB	Output is correct
72	Correct	1156 ms	210512 KB	Output is correct
73	Correct	1187 ms	218020 KB	Output is correct
74	Correct	1105 ms	225324 KB	Output is correct
75	Correct	906 ms	233036 KB	Output is correct
76	Correct	769 ms	241316 KB	Output is correct
77	Correct	848 ms	250796 KB	Output is correct
78	Runtime error	467 ms	263096 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.

답안 #90874

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 33.0 / 33.0

Subtask #3 0 / 48.0

Subtask #1
19.0 / 19.0

Subtask #2
33.0 / 33.0

Subtask #3
0 / 48.0