Submission #1007752
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mod 1000000007
#define INF_LL 1145141919810364
#define MAX_N 200005
#define MAX_Q 200005
int N, Q;
LL A[MAX_Q], B[MAX_Q], C[MAX_Q];
void input()
{
cin >> N >> Q;
for (size_t i = 0; i < Q; i++) {
scanf("%lld %lld %lld", &A[i], &B[i], &C[i]);
}
}
class UnionFind{
public:
UnionFind(int _n)
{
init(_n);
}
void init(int _n)
{
par.clear();
par.resize(_n);
for (size_t i = 0; i < par.size(); i++) {
par[i] = i;
}
}
int find(int _x)
{
if(_x == par[_x]){
return _x;
}
else{
return par[_x] = find(par[_x]);
}
}
void unite(int _x, int _y)
{
_x = find(_x);
_y = find(_y);
if(_x == _y){
return;
}
par[_x] = _y;
}
bool same(int _x, int _y)
{
return find(_x) == find(_y);
}
private:
vector<int> par;
};
LL dp[MAX_N][2];
LL Cost[MAX_N];
vector<pair<LL, pair<int, int>>> EdgeList;
LL solve()
{
for (size_t i = 0; i < N; i++) {
Cost[i] = INF_LL;
}
for (size_t i = 0; i < Q; i++) {
Cost[A[i]] = min(Cost[A[i]], C[i]+1);
Cost[B[i]] = min(Cost[B[i]], C[i]+2);
}
for (size_t d = 0; d < 2; d++) {
for (size_t i = 0; i < N; i++) {
Cost[(i+1)%N] = min(Cost[(i+1)%N], Cost[i]+2);
}
}
UnionFind uf(N);
for (size_t i = 0; i < Q; i++) {
EdgeList.push_back(make_pair(C[i], make_pair(A[i], B[i])));
}
for (size_t i = 0; i < N; i++) {
EdgeList.push_back(make_pair(Cost[i], make_pair(i, (i+1)%N)));
}
sort(EdgeList.begin(), EdgeList.end());
LL ret = 0;
for (size_t i = 0; i < EdgeList.size(); i++) {
auto edge = EdgeList[i];
if(!uf.same(edge.second.first, edge.second.second)){
uf.unite(edge.second.first, edge.second.second);
ret += edge.first;
}
}
return ret;
}
int main()
{
input();
cout << solve() << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
takoshi |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
2031 Byte |
Status |
AC |
Exec Time |
137 ms |
Memory |
15596 KB |
Compile Error
./Main.cpp: In function ‘void input()’:
./Main.cpp:20:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &A[i], &B[i], &C[i]);
^
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 |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
3 ms |
256 KB |
01-02.txt |
AC |
79 ms |
9200 KB |
01-03.txt |
AC |
124 ms |
15596 KB |
01-04.txt |
AC |
37 ms |
7276 KB |
01-05.txt |
AC |
29 ms |
6768 KB |
01-06.txt |
AC |
34 ms |
6768 KB |
01-07.txt |
AC |
33 ms |
6768 KB |
01-08.txt |
AC |
36 ms |
6896 KB |
01-09.txt |
AC |
43 ms |
7024 KB |
01-10.txt |
AC |
88 ms |
13292 KB |
01-11.txt |
AC |
111 ms |
14444 KB |
01-12.txt |
AC |
131 ms |
15596 KB |
01-13.txt |
AC |
131 ms |
15596 KB |
01-14.txt |
AC |
131 ms |
15596 KB |
01-15.txt |
AC |
133 ms |
15596 KB |
01-16.txt |
AC |
131 ms |
15596 KB |
01-17.txt |
AC |
131 ms |
15596 KB |
01-18.txt |
AC |
105 ms |
15596 KB |
01-19.txt |
AC |
32 ms |
6768 KB |
01-20.txt |
AC |
45 ms |
6896 KB |
01-21.txt |
AC |
72 ms |
8176 KB |
01-22.txt |
AC |
131 ms |
15596 KB |
01-23.txt |
AC |
132 ms |
15596 KB |
01-24.txt |
AC |
33 ms |
8172 KB |
01-25.txt |
AC |
124 ms |
15596 KB |
01-26.txt |
AC |
39 ms |
7660 KB |
01-27.txt |
AC |
46 ms |
7148 KB |
01-28.txt |
AC |
99 ms |
13804 KB |
01-29.txt |
AC |
117 ms |
14572 KB |
01-30.txt |
AC |
137 ms |
15596 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |
sample-03.txt |
AC |
3 ms |
256 KB |