Submission #1817601


Source Code Expand

Copy
#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 Info

Submission Time
Task G - Zigzag MST
User munaiyi
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1310 Byte
Status
Exec Time 214 ms
Memory 40320 KB

Compile Error

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

Judge Result

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