Submission #10066140
Source Code Expand
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; struct unionfind{ vector<int> par, sz; unionfind() {} unionfind(int n):par(n), sz(n, 1){ for(int i=0; i<n; i++) par[i]=i; } int find(int x){ if(par[x]==x) return x; return par[x]=find(par[x]); } void unite(int x, int y){ x=find(x); y=find(y); if(x==y) return; if(sz[x]>sz[y]) swap(x, y); par[x]=y; sz[y]+=sz[x]; } bool same(int x, int y){ return find(x)==find(y); } int size(int x){ return sz[find(x)]; } }; int main() { int n, q; cin>>n>>q; int a[200020], b[200020]; ll c[200020]; using edge=pair<ll, P>; vector<edge> v; ll mn[200020]; const ll INF=1e18; fill(mn, mn+n, INF); ll d=INF; for(int i=0; i<q; i++){ cin>>a[i]>>b[i]>>c[i]; d=min(d, c[i]+1+2*(n-a[i])); mn[a[i]]=min(mn[a[i]], c[i]+1); d=min(d, c[i]+2+2*(n-b[i])); mn[b[i]]=min(mn[b[i]], c[i]+2); v.push_back({c[i], {a[i], b[i]}}); } for(int i=0; i<n; i++){ d=min(d, mn[i]); v.push_back({d, {i, (i+1)%n}}); d+=2; } sort(v.begin(), v.end()); unionfind uf(n); ll ans=0; for(auto e:v){ int x=e.second.first, y=e.second.second; if(!uf.same(x, y)){ uf.unite(x, y); ans+=e.first; } } cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - Zigzag MST |
User | chocorusk |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 1880 Byte |
Status | AC |
Exec Time | 267 ms |
Memory | 15084 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 | 4352 KB |
01-02.txt | AC | 163 ms | 9328 KB |
01-03.txt | AC | 267 ms | 13676 KB |
01-04.txt | AC | 24 ms | 9584 KB |
01-05.txt | AC | 16 ms | 8944 KB |
01-06.txt | AC | 21 ms | 9840 KB |
01-07.txt | AC | 20 ms | 9840 KB |
01-08.txt | AC | 22 ms | 9968 KB |
01-09.txt | AC | 33 ms | 8428 KB |
01-10.txt | AC | 132 ms | 13292 KB |
01-11.txt | AC | 225 ms | 12780 KB |
01-12.txt | AC | 243 ms | 14316 KB |
01-13.txt | AC | 243 ms | 13676 KB |
01-14.txt | AC | 249 ms | 14956 KB |
01-15.txt | AC | 245 ms | 13548 KB |
01-16.txt | AC | 240 ms | 13292 KB |
01-17.txt | AC | 241 ms | 13292 KB |
01-18.txt | AC | 221 ms | 15084 KB |
01-19.txt | AC | 19 ms | 9968 KB |
01-20.txt | AC | 28 ms | 9712 KB |
01-21.txt | AC | 77 ms | 10348 KB |
01-22.txt | AC | 197 ms | 13804 KB |
01-23.txt | AC | 199 ms | 14316 KB |
01-24.txt | AC | 27 ms | 8812 KB |
01-25.txt | AC | 241 ms | 15084 KB |
01-26.txt | AC | 25 ms | 7664 KB |
01-27.txt | AC | 36 ms | 8172 KB |
01-28.txt | AC | 159 ms | 13164 KB |
01-29.txt | AC | 228 ms | 14188 KB |
01-30.txt | AC | 244 ms | 14700 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 |