CODE FESTIVAL 2016 Final

Submission #1817601

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int a[maxn],b[maxn],c[maxn];
vector<int> x[maxn<<1],y[maxn<<1];
void add(int u,int v,int w)
{
    if(u==v) return ;
    x[w].push_back(u);
    y[w].push_back(v);
}
int fa[maxn];
int findfa(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=findfa(fa[x]);
}
int main()
{
    int n,q;
    int mn=1000000000;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",a+i,b+i,c+i);
        mn=min(mn,c[i]);
    }
    long long ans=1LL*mn*(n-1);
    for(int i=1;i<=q;i++)
    {
        if(c[i]>mn+2*n) continue;
        c[i]-=mn;
        a[i]++;b[i]++;
        add(a[i],b[i],c[i]);
        a[i]++;
        if(a[i]>n) a[i]-=n;
        add(a[i],b[i],c[i]+1);

    }
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=0;i<=2*n;i++)
    {
        for(int j=0;j<x[i].size();j++)
        {
            int tx=x[i][j],ty=y[i][j];
            int fx=findfa(tx),fy=findfa(ty);
            if(fx==fy) continue;
            //printf("%d %d %d\n",tx-1,ty-1,i);
            fa[fx]=fy;
            tx++;ty++;
            ans+=i;
            if(tx>n) tx-=n;
            if(ty>n) ty-=n;
            add(tx,ty,i+2);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Submission

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

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:22:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
^
./Main.cpp:25:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",a+i,b+i,c+i);
^

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 7 ms 19968 KB
01-02.txt AC 52 ms 21376 KB
01-03.txt AC 83 ms 27520 KB
01-04.txt AC 32 ms 34432 KB
01-05.txt AC 32 ms 33152 KB
01-06.txt AC 31 ms 31488 KB
01-07.txt AC 29 ms 24832 KB
01-08.txt AC 24 ms 24192 KB
01-09.txt AC 32 ms 24448 KB
01-10.txt AC 125 ms 33408 KB
01-11.txt AC 174 ms 34048 KB
01-12.txt AC 211 ms 40192 KB
01-13.txt AC 205 ms 40192 KB
01-14.txt AC 208 ms 40320 KB
01-15.txt AC 213 ms 40320 KB
01-16.txt AC 211 ms 40192 KB
01-17.txt AC 214 ms 40320 KB
01-18.txt AC 85 ms 36204 KB
01-19.txt AC 31 ms 27392 KB
01-20.txt AC 19 ms 22912 KB
01-21.txt AC 41 ms 23620 KB
01-22.txt AC 86 ms 27604 KB
01-23.txt AC 86 ms 27604 KB
01-24.txt AC 35 ms 33280 KB
01-25.txt AC 99 ms 34560 KB
01-26.txt AC 28 ms 27008 KB
01-27.txt AC 32 ms 28032 KB
01-28.txt AC 71 ms 30816 KB
01-29.txt AC 82 ms 29260 KB
01-30.txt AC 96 ms 32580 KB
sample-01.txt AC 7 ms 19968 KB
sample-02.txt AC 7 ms 19968 KB
sample-03.txt AC 7 ms 19968 KB