Submission #1003862
Source Code Expand
#pragma GCC optimize("O3")
#pragma GCC target("sse4.2")
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef int Weight;
struct Edge {
int src, dst;
Weight weight;
Edge(int src, int dst, Weight weight) :
src(src), dst(dst), weight(weight) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef pair<Weight, int> Result;
Result visit(int p, int v, const Graph &g) {
int f = g[v].size()==2;
Result r(0, v);
for(auto &e: g[v]) if (e.dst != p) {
Result t = visit(v, e.dst, g);
t.first += f; //e->weight;
if (r.first < t.first) r = t;
}
return r;
}
Weight diameter(const Graph &g) {
Result r = visit(-1, 0, g);
Result t = visit(-1, r.second, g);
return t.first; // (r.second, t.second) is farthest pair
}
int main(){
int V,s,t;
scanf("%d",&V);
Graph g(V);
for(;V>1;V--)scanf("%d%d",&s,&t),s--,t--,g[s].push_back(Edge(s,t,1)),g[t].push_back(Edge(t,s,1));
printf("%d\n",diameter(g)+count_if(g.begin(),g.end(),[](auto &e){return e.size()==1;}));
}
Submission Info
Submission Time
2016-11-30 14:23:34+0900
Task
K - Problem on Tree
User
leafmoon
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
1077 Byte
Status
AC
Exec Time
50 ms
Memory
6656 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:41:88: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::__iterator_traits<__gnu_cxx::__normal_iterator<std::vector<Edge>*, std::vector<std::vector<Edge> > >, void>::difference_type {aka long int}’ [-Wformat=]
printf("%d\n",diameter(g)+count_if(g.begin(),g.end(),[](auto &e){return e.size()==1;}));
^
./Main.cpp:38:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&V);
^
./Main.cpp:40:98: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(;V>1;V--)scanf("%d%d",&s,&t),s--,t--,g[s].push_back(Edge(s,t,1)),g[t].push_back(Edge(t,s,1));
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
100 / 100
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt
All
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
2 ms
256 KB
sample_02.txt
AC
2 ms
256 KB
subtask1_01.txt
AC
41 ms
5632 KB
subtask1_02.txt
AC
32 ms
4480 KB
subtask1_03.txt
AC
15 ms
2048 KB
subtask1_04.txt
AC
18 ms
2560 KB
subtask1_05.txt
AC
22 ms
3072 KB
subtask1_06.txt
AC
4 ms
512 KB
subtask1_07.txt
AC
48 ms
6656 KB
subtask1_08.txt
AC
14 ms
1920 KB
subtask1_09.txt
AC
30 ms
4224 KB
subtask1_10.txt
AC
38 ms
5376 KB
subtask1_11.txt
AC
18 ms
2560 KB
subtask1_12.txt
AC
8 ms
1152 KB
subtask1_13.txt
AC
5 ms
768 KB
subtask1_14.txt
AC
6 ms
768 KB
subtask1_15.txt
AC
49 ms
6656 KB
subtask1_16.txt
AC
49 ms
6656 KB
subtask1_17.txt
AC
49 ms
6656 KB
subtask1_18.txt
AC
49 ms
6656 KB
subtask1_19.txt
AC
49 ms
6656 KB
subtask1_20.txt
AC
49 ms
6656 KB
subtask1_21.txt
AC
49 ms
6656 KB
subtask1_22.txt
AC
49 ms
6656 KB
subtask1_23.txt
AC
49 ms
6656 KB
subtask1_24.txt
AC
49 ms
6656 KB
subtask1_25.txt
AC
49 ms
6656 KB
subtask1_26.txt
AC
49 ms
6656 KB
subtask1_27.txt
AC
49 ms
6656 KB
subtask1_28.txt
AC
49 ms
6656 KB
subtask1_29.txt
AC
49 ms
6656 KB
subtask1_30.txt
AC
49 ms
6656 KB
subtask1_31.txt
AC
49 ms
6656 KB
subtask1_32.txt
AC
49 ms
6656 KB
subtask1_33.txt
AC
49 ms
6656 KB
subtask1_34.txt
AC
49 ms
6656 KB
subtask1_35.txt
AC
50 ms
6656 KB
subtask1_36.txt
AC
49 ms
6656 KB
subtask1_37.txt
AC
49 ms
6656 KB
subtask1_38.txt
AC
50 ms
6656 KB
subtask1_39.txt
AC
49 ms
6656 KB