CODE FESTIVAL 2016 Final

Submission #1200439

Source codeソースコード

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

typedef long long i64;

const int N = 200000 + 10;

struct Edge {
  int x, y, z;
  Edge() {}
  Edge(int _x, int _y, int _z): x(_x), y(_y), z(_z) {}
  inline bool operator< (const Edge &rhs) const {
    return z < rhs.z;
  }
};

inline void check(int &lhs, int rhs) { lhs = (lhs < rhs ? lhs : rhs); }

int n, tag[N];
std::vector<Edge> edge;

void init() {
  int m;
  scanf("%d%d", &n, &m);
  memset(tag, 0x3f, sizeof tag);
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    edge.push_back(Edge(a, b, c));
    check(tag[a], c + 1);
    check(tag[b], c + 2);
  }
  for (int i = 0; i < 3 * n; ++i) check(tag[(i + 1) % n], tag[i % n] + 2);
}

int anc[N];
int find(int x) { return anc[x] == x ? x : (anc[x] = find(anc[x])); }

int main() {
  init();
  for (int i = 0; i < n; ++i) edge.push_back(Edge(i, (i + 1) % n, tag[i]));
  std::sort(edge.begin(), edge.end());
  for (int i = 0; i < n; ++i) anc[i] = i;
  i64 ans = 0;
  for (int i = 0; i < edge.size(); ++i) {
    int x = find(edge[i].x), y = find(edge[i].y), z = edge[i].z;
    if (x != y) anc[x] = y, ans += z;
  }
  printf("%lld\n", ans);
  return 0;
}

Submission

Task問題 G - Zigzag MST
User nameユーザ名 jiaqiyang
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1300
Source lengthソースコード長 1253 Byte
File nameファイル名
Exec time実行時間 96 ms
Memory usageメモリ使用量 10604 KB

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

./Main.cpp: In function ‘void init()’:
./Main.cpp:26:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:30:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
^

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 1300 / 1300 sample-01.txt,sample-02.txt,sample-03.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,sample-01.txt,sample-02.txt,sample-03.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 1024 KB
01-02.txt AC 64 ms 4212 KB
01-03.txt AC 94 ms 7664 KB
01-04.txt AC 23 ms 6640 KB
01-05.txt AC 15 ms 5744 KB
01-06.txt AC 19 ms 6128 KB
01-07.txt AC 18 ms 5748 KB
01-08.txt AC 18 ms 5748 KB
01-09.txt AC 24 ms 4464 KB
01-10.txt AC 59 ms 7664 KB
01-11.txt AC 83 ms 8944 KB
01-12.txt AC 95 ms 8176 KB
01-13.txt AC 95 ms 9072 KB
01-14.txt AC 95 ms 7664 KB
01-15.txt AC 96 ms 8944 KB
01-16.txt AC 96 ms 7664 KB
01-17.txt AC 94 ms 8432 KB
01-18.txt AC 73 ms 10604 KB
01-19.txt AC 17 ms 5748 KB
01-20.txt AC 22 ms 4336 KB
01-21.txt AC 42 ms 4976 KB
01-22.txt AC 83 ms 8688 KB
01-23.txt AC 83 ms 7920 KB
01-24.txt AC 18 ms 8176 KB
01-25.txt AC 94 ms 9708 KB
01-26.txt AC 23 ms 6896 KB
01-27.txt AC 26 ms 6000 KB
01-28.txt AC 63 ms 8304 KB
01-29.txt AC 79 ms 7788 KB
01-30.txt AC 93 ms 8304 KB
sample-01.txt AC 1 ms 1024 KB
sample-02.txt AC 1 ms 1024 KB
sample-03.txt AC 1 ms 1024 KB