Submission #5397163
Source Code Expand
#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define eps 1e-10 #define MAXN 200005 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) { res = 0;T f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 +c - '0'; c = getchar(); } res *= f; } template<class T> void out(T x) { if(x < 0) {x = -x;putchar('-');} if(x >= 10) { out(x / 10); } putchar('0' + x % 10); } struct node { int u,v; int64 c; }E[MAXN * 2]; int N,Q,tot; int64 val[MAXN * 2]; int fa[MAXN]; int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); } void Solve() { read(N);read(Q); int a,b;int64 c; for(int i = 0 ; i < 2 * N ; ++i) val[i] = 1e18; for(int i = 1 ; i <= Q ; ++i) { read(a);read(b);read(c); E[++tot] = (node){a,b,c}; val[a] = min(val[a],c + 1); val[b] = min(val[b],c + 2); } for(int i = 1 ; i < 2 * N ; ++i) { val[i] = min(val[i - 1] + 2,val[i]); } for(int i = 0 ; i < N ; ++i) { E[++tot] = (node){i,(i + 1) % N,min(val[i],val[i + N])}; } sort(E + 1,E + tot + 1,[](node a,node b){return a.c < b.c;}); for(int i = 0 ; i < N ; ++i) fa[i] = i; int64 ans = 0; for(int i = 1 ; i <= tot ; ++i) { if(getfa(E[i].u) != getfa(E[i].v)) { fa[getfa(E[i].u)] = getfa(E[i].v); ans += E[i].c; } } out(ans);enter; } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - Zigzag MST |
User | sigongzi |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 1810 Byte |
Status | AC |
Exec Time | 78 ms |
Memory | 13568 KB |
Judge Result
Set Name | sample | all | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1300 / 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 | 2 ms | 2304 KB |
01-02.txt | AC | 40 ms | 6400 KB |
01-03.txt | AC | 76 ms | 10624 KB |
01-04.txt | AC | 22 ms | 10752 KB |
01-05.txt | AC | 14 ms | 9472 KB |
01-06.txt | AC | 18 ms | 9984 KB |
01-07.txt | AC | 17 ms | 8832 KB |
01-08.txt | AC | 18 ms | 8576 KB |
01-09.txt | AC | 22 ms | 8448 KB |
01-10.txt | AC | 48 ms | 8832 KB |
01-11.txt | AC | 63 ms | 8448 KB |
01-12.txt | AC | 77 ms | 10368 KB |
01-13.txt | AC | 76 ms | 10368 KB |
01-14.txt | AC | 78 ms | 10368 KB |
01-15.txt | AC | 78 ms | 10368 KB |
01-16.txt | AC | 77 ms | 10368 KB |
01-17.txt | AC | 76 ms | 10368 KB |
01-18.txt | AC | 54 ms | 13568 KB |
01-19.txt | AC | 17 ms | 8704 KB |
01-20.txt | AC | 21 ms | 8448 KB |
01-21.txt | AC | 35 ms | 8448 KB |
01-22.txt | AC | 60 ms | 10368 KB |
01-23.txt | AC | 60 ms | 10368 KB |
01-24.txt | AC | 16 ms | 11520 KB |
01-25.txt | AC | 74 ms | 13568 KB |
01-26.txt | AC | 22 ms | 11008 KB |
01-27.txt | AC | 24 ms | 9984 KB |
01-28.txt | AC | 50 ms | 10752 KB |
01-29.txt | AC | 59 ms | 9600 KB |
01-30.txt | AC | 71 ms | 11904 KB |
sample-01.txt | AC | 2 ms | 2304 KB |
sample-02.txt | AC | 2 ms | 2304 KB |
sample-03.txt | AC | 2 ms | 2304 KB |