Submission #993640
Source Code Expand
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif
typedef long long int int64;
const int N = (int) 4e5 + 100;
vector <pair <int, int> > g[N];
int par[N];
int sz[N];
int getP(int x)
{
if (par[x] == x) return x;
return par[x] = getP(par[x] );
}
bool add(int a, int b)
{
a = getP(a);
b = getP(b);
if (a == b) return false;
if (sz[a] > sz[b] )
{
sz[a] += sz[b];
par[b] = a;
}
else
{
sz[b] += sz[a];
par[a] = b;
}
return true;
}
int a[N], b[N], c[N];
int main(int, char **)
{
#ifdef LOCAL
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, q;
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++)
{
sz[i] = 1;
par[i] = i;
}
int minC = (int) 1e9 + 100;
for (int i = 0; i < q; i++)
{
scanf("%d%d%d", &a[i], &b[i], &c[i]);
minC = min(minC, c[i] );
}
long long ans = (n - 1) * 1LL * minC;
for (int i = 0; i < q; i++)
{
if (c[i] - minC > n) continue;
g[c[i] - minC].emplace_back(a[i], b[i]);
g[c[i] - minC + 1].emplace_back( (a[i] + 1) % n, b[i]);
}
for (int i = 0; i < N; i++)
{
for (auto p : g[i] )
{
// eprintf(">>> %d %d\n", p.first, p.second);
if (add(p.first, p.second) )
{
// eprintf("%d : %d %d\n", i, p.first, p.second);
ans += i;
g[i + 2].emplace_back((p.first + 1) % n, (p.second + 1) % n);
}
}
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
Merkurev |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
1741 Byte |
Status |
AC |
Exec Time |
120 ms |
Memory |
22912 KB |
Compile Error
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:61:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
^
./Main.cpp:72:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &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 |
13 ms |
9600 KB |
01-02.txt |
AC |
61 ms |
12032 KB |
01-03.txt |
AC |
85 ms |
16896 KB |
01-04.txt |
AC |
32 ms |
17408 KB |
01-05.txt |
AC |
32 ms |
17152 KB |
01-06.txt |
AC |
31 ms |
16384 KB |
01-07.txt |
AC |
28 ms |
14080 KB |
01-08.txt |
AC |
27 ms |
13952 KB |
01-09.txt |
AC |
29 ms |
13952 KB |
01-10.txt |
AC |
73 ms |
17152 KB |
01-11.txt |
AC |
99 ms |
17408 KB |
01-12.txt |
AC |
117 ms |
19968 KB |
01-13.txt |
AC |
120 ms |
20096 KB |
01-14.txt |
AC |
113 ms |
20096 KB |
01-15.txt |
AC |
116 ms |
20096 KB |
01-16.txt |
AC |
116 ms |
20096 KB |
01-17.txt |
AC |
115 ms |
20096 KB |
01-18.txt |
AC |
98 ms |
22884 KB |
01-19.txt |
AC |
29 ms |
14848 KB |
01-20.txt |
AC |
26 ms |
13312 KB |
01-21.txt |
AC |
45 ms |
14452 KB |
01-22.txt |
AC |
90 ms |
19684 KB |
01-23.txt |
AC |
91 ms |
19684 KB |
01-24.txt |
AC |
37 ms |
18048 KB |
01-25.txt |
AC |
99 ms |
22912 KB |
01-26.txt |
AC |
28 ms |
14336 KB |
01-27.txt |
AC |
34 ms |
15488 KB |
01-28.txt |
AC |
72 ms |
18648 KB |
01-29.txt |
AC |
90 ms |
18372 KB |
01-30.txt |
AC |
99 ms |
20804 KB |
sample-01.txt |
AC |
13 ms |
9600 KB |
sample-02.txt |
AC |
13 ms |
9600 KB |
sample-03.txt |
AC |
13 ms |
9600 KB |