CODE FESTIVAL 2016 Relay (Parallel)

Submission #1003862

Source codeソースコード

#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

Task問題 K - 木の問題 / Problem on Tree
User nameユーザ名 002_ciel
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1077 Byte
File nameファイル名
Exec time実行時間 50 ms
Memory usageメモリ使用量 6656 KB

Compiler messageコンパイルメッセージ

./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));
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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