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 |
|
|
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 |