Submission #6878281
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll
#define INF 1e16
#define mod 1000000007
struct UnionFind{
vector<int> v;
UnionFind(int n) : v(n, -1) {}
void init(){ for(int i = 0;i < (int)v.size();i++)v[i]=-1; }
int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (-v[x] < -v[y]) swap(x, y);
v[x] += v[y]; v[y] = x;
return true;
}
bool root(int x) { return v[x] < 0; }
bool same(int x, int y) { return find(x) == find(y); }
int size(int x) { return -v[find(x)]; }
};
struct edge{
ll u,v,cost;
};
ll n,q;
vector<ll> a,b,c;
vector<edge> es;
vector<vector<ll>> bs;
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin>>n>>q;
a.resize(q); b.resize(q); c.resize(q);
bs.resize(2*n);
rep(i,q){
cin>>a[i]>>b[i]>>c[i];
es.push_back((edge){a[i],b[i],c[i]});
bs[a[i]].push_back(c[i]+1);
if(a[i]+n<2*n) bs[a[i]+n].push_back(c[i]+1);
bs[b[i]].push_back(c[i]+2);
if(b[i]+n<2*n) bs[b[i]+n].push_back(c[i]+2);
}
ll mn=INF;
rep(i,2*n-1){
for(ll bb : bs[i]){
minch(mn,bb);
}
es.push_back((edge){i%n,(i+1)%n,mn});
mn+=2;
}
sort(all(es),[](const edge& a,const edge& b){
return a.cost < b.cost;
});
ll res=0;
UnionFind uf(n);
rep(i,es.size()){
if(uf.unite(es[i].u,es[i].v)){
res+=es[i].cost;
}
}
cout<<res<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
yamad |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
2052 Byte |
Status |
AC |
Exec Time |
265 ms |
Memory |
54696 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 |
1 ms |
256 KB |
01-02.txt |
AC |
75 ms |
18580 KB |
01-03.txt |
AC |
239 ms |
54312 KB |
01-04.txt |
AC |
46 ms |
23276 KB |
01-05.txt |
AC |
51 ms |
23916 KB |
01-06.txt |
AC |
43 ms |
24044 KB |
01-07.txt |
AC |
40 ms |
22644 KB |
01-08.txt |
AC |
43 ms |
24220 KB |
01-09.txt |
AC |
52 ms |
25260 KB |
01-10.txt |
AC |
142 ms |
33452 KB |
01-11.txt |
AC |
206 ms |
35372 KB |
01-12.txt |
AC |
250 ms |
53928 KB |
01-13.txt |
AC |
259 ms |
54184 KB |
01-14.txt |
AC |
259 ms |
54440 KB |
01-15.txt |
AC |
265 ms |
54440 KB |
01-16.txt |
AC |
254 ms |
54568 KB |
01-17.txt |
AC |
265 ms |
53544 KB |
01-18.txt |
AC |
122 ms |
46476 KB |
01-19.txt |
AC |
42 ms |
23148 KB |
01-20.txt |
AC |
42 ms |
23212 KB |
01-21.txt |
AC |
92 ms |
28972 KB |
01-22.txt |
AC |
237 ms |
54440 KB |
01-23.txt |
AC |
229 ms |
54696 KB |
01-24.txt |
AC |
62 ms |
24108 KB |
01-25.txt |
AC |
154 ms |
52008 KB |
01-26.txt |
AC |
46 ms |
23788 KB |
01-27.txt |
AC |
57 ms |
23468 KB |
01-28.txt |
AC |
146 ms |
34220 KB |
01-29.txt |
AC |
193 ms |
35628 KB |
01-30.txt |
AC |
230 ms |
52008 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 |