CODE FESTIVAL 2016 Final

Submission #1178677

Source codeソースコード

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const int ESIZE = MAXN << 1;
const ll INF = 2e9;
int n, Q, tot;
ll s[MAXN], t[MAXN];
int bel[MAXN], rk[MAXN];
ll ans;

struct like {
    int u, v; ll c;
    bool operator < (const like &r) const {
        return c < r.c;
    }
} e[ESIZE];

int find(int p) {
    return p == bel[p] ? p : bel[p] = find(bel[p]);
}

void Union(int x, int y) {
    if (rk[x] < rk[y])
        swap(x, y);
    if (rk[x] == rk[y])
        rk[x]++;
    bel[y] = x;
}

int main() {
    scanf("%d %d", &n, &Q);
    for (int i = 0; i < n; i++)
        s[i] = t[i] = INF, bel[i] = i;
    int a, b; ll c, x = INF;
    for (int i = 1; i <= Q; i++) {
        scanf("%d %d %lld", &a, &b, &c);
        e[i] = (like){a, b, c};
        s[a] = min(s[a], c + 1), s[b] = min(s[b], c + 2);
    }
    tot = Q;
    for (int i = 0; i < n << 1; i++, x = min(x + 2, INF))
        if ((x = min(x, s[i % n])) != INF)
            t[i % n] = min(t[i % n], x);
    for (int i = 1; i < n; i++)
        if (t[i - 1] != INF)
            e[++tot] = (like){i - 1, i, t[i - 1]};
    if (t[n - 1] != INF)
        e[++tot] = (like){n - 1, 0, t[n - 1]};
    sort(e + 1, e + tot + 1);
    for (int i = 1, r1, r2; i <= tot; i++)
        if ((r1 = find(e[i].u)) != (r2 = find(e[i].v))) {
            ans += e[i].c;
            Union(r1, r2);
        }
    printf("%lld", ans);
    return 0;
}

Submission

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

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:36:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &Q);
^
./Main.cpp:41:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld", &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 4224 KB
01-02.txt AC 66 ms 8320 KB
01-03.txt AC 92 ms 11136 KB
01-04.txt AC 19 ms 9088 KB
01-05.txt AC 13 ms 9088 KB
01-06.txt AC 16 ms 9088 KB
01-07.txt AC 14 ms 9088 KB
01-08.txt AC 15 ms 9088 KB
01-09.txt AC 18 ms 9088 KB
01-10.txt AC 53 ms 11136 KB
01-11.txt AC 81 ms 10368 KB
01-12.txt AC 91 ms 11136 KB
01-13.txt AC 91 ms 11136 KB
01-14.txt AC 90 ms 11136 KB
01-15.txt AC 92 ms 11136 KB
01-16.txt AC 91 ms 11136 KB
01-17.txt AC 91 ms 11136 KB
01-18.txt AC 72 ms 11136 KB
01-19.txt AC 14 ms 9088 KB
01-20.txt AC 15 ms 9088 KB
01-21.txt AC 31 ms 9088 KB
01-22.txt AC 72 ms 11136 KB
01-23.txt AC 72 ms 11136 KB
01-24.txt AC 15 ms 9088 KB
01-25.txt AC 93 ms 11136 KB
01-26.txt AC 19 ms 9088 KB
01-27.txt AC 20 ms 9088 KB
01-28.txt AC 55 ms 11136 KB
01-29.txt AC 74 ms 10368 KB
01-30.txt AC 82 ms 11136 KB
sample-01.txt AC 1 ms 4224 KB
sample-02.txt AC 1 ms 4224 KB
sample-03.txt AC 1 ms 4224 KB