Submission #5018397


Source Code Expand

#include <bits/stdc++.h>
#define mem(s,t) memset(s,t,sizeof(s))
#define pb(s) push_back(s)
#define inf 0x3f3f3f3f
#define mn 100010
typedef long long ll;
using namespace std;
struct X
{
    ll u,v;
    ll c;
    bool operator <(const X &x)const
    {
        return c<x.c;
    }
}x[200010];
struct edge
{
    ll u,v;
    ll w;
    bool operator <(const edge &x)const
    {
        return w>x.w;
    }
};
priority_queue<edge> q;
ll n,m;
ll f[200010];
ll sf(ll x)
{
    return x==f[x]?x:f[x]=sf(f[x]);
}
ll ans;
ll maxx;
void add(ll p)
{
    ll i,j,k;
    if (x[p].u==x[p].v)
    {
        for (i=1;i<=n-1;i++)
        {
            edge e;
            k=i*2;
            if (k%2==1)
            {
                e.u=(x[p].u+k/2)%n;
                e.v=(x[p].v+k/2)%n;
            }
            else
            {
                e.u=(x[p].v+(k-2)/2)%n;
                e.v=(x[p].u+k/2)%n;
            }
            e.w=x[p].c+k-1;
            if (p==1) maxx=max(maxx,e.w);
            if (p!=1&&e.w>=maxx) break;
            q.push(e);
        }
    }
    else
    {
        j=(x[p].v+n-x[p].u)%n;
        for (i=1;i<=min(2*j-1,n-1);i++)
        {
            edge e;
            k=i;
            if (k%2==1)
            {
                e.u=(x[p].u+k/2)%n;
                e.v=(x[p].v+k/2)%n;
            }
            else
            {
                e.u=(x[p].v+(k-2)/2)%n;
                e.v=(x[p].u+k/2)%n;
            }
            e.w=x[p].c+k-1;
            if (p==1) maxx=max(maxx,e.w);
            if (p!=1&&e.w>=maxx) break;
            q.push(e);
        }
        for (i=2*j+1;i<=2*(n-j)-1;i++)
        {
            edge e;
            k=i;
            if (k%2==1)
            {
                e.u=(x[p].u+k/2)%n;
                e.v=(x[p].v+k/2)%n;
            }
            else
            {
                e.u=(x[p].v+(k-2)/2)%n;
                e.v=(x[p].u+k/2)%n;
            }
            e.w=x[p].c+k-1;
            if (p==1) maxx=max(maxx,e.w);
            if (p!=1&&e.w>=maxx) break;
            q.push(e);
        }
    }
}

int main()
{
    ll i,j,k;
    cin>>n>>m;
    for (i=1;i<=n;i++)
        f[i]=i;
    for (i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&x[i].u,&x[i].v,&x[i].c);
    }
    sort(x+1,x+m+1);
    ll cnt=0;
    ans=0;
    maxx=0;
    add(1);
    for (i=2;i<=m;i++)
    {
        while (q.top().w<=x[i].c)
        {
            edge e=q.top();
            q.pop();
            if (sf(e.u)!=sf(e.v))
            {
                cnt++;
                f[sf(e.u)]=sf(e.v);
                ans+=e.w;
            }
            if (cnt==n-1) break;
        }
        if (cnt==n-1) break;
        add(i);
    }
    while (cnt<n-1)
    {
        edge e=q.top();
        q.pop();
        if (sf(e.u)!=sf(e.v))
        {
            cnt++;
            f[sf(e.u)]=sf(e.v);
            ans+=e.w;
        }
        if (cnt==n-1) break;
    }
    cout<<ans<<endl;
    return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User vjudge4
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2925 Byte
Status TLE
Exec Time 2344 ms
Memory 1581520 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:112:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld",&x[i].u,&x[i].v,&x[i].c);
                                                        ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 1300
Status
AC × 3
AC × 14
TLE × 21
MLE × 1
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 AC 1 ms 256 KB
01-02.txt AC 59 ms 4992 KB
01-03.txt AC 404 ms 106464 KB
01-04.txt TLE 2104 ms 9712 KB
01-05.txt AC 76 ms 14956 KB
01-06.txt AC 87 ms 15084 KB
01-07.txt AC 270 ms 101728 KB
01-08.txt MLE 1245 ms 397272 KB
01-09.txt TLE 2344 ms 1184976 KB
01-10.txt TLE 2120 ms 1577936 KB
01-11.txt TLE 2114 ms 1579728 KB
01-12.txt TLE 2112 ms 1580112 KB
01-13.txt TLE 2112 ms 1581008 KB
01-14.txt TLE 2112 ms 1581520 KB
01-15.txt TLE 2112 ms 1581520 KB
01-16.txt TLE 2111 ms 1580368 KB
01-17.txt TLE 2110 ms 1580112 KB
01-18.txt TLE 2110 ms 1579856 KB
01-19.txt AC 155 ms 51684 KB
01-20.txt TLE 2109 ms 1576784 KB
01-21.txt TLE 2109 ms 1577936 KB
01-22.txt TLE 2109 ms 1581392 KB
01-23.txt TLE 2109 ms 1579984 KB
01-24.txt TLE 2109 ms 1576656 KB
01-25.txt TLE 2110 ms 1581264 KB
01-26.txt AC 50 ms 15596 KB
01-27.txt TLE 2109 ms 1576784 KB
01-28.txt TLE 2109 ms 1580496 KB
01-29.txt TLE 2109 ms 1578832 KB
01-30.txt TLE 2109 ms 1580240 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB