Submission #993664


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 100005;

int p[maxn], s[maxn];
set<pair<int, pair<int, int>>> edges;
int n, m;

inline int find(int a)
{
    return p[a] == a ? a : p[a] = find(p[a]);
}

inline bool unite(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (s[a] < s[b]) swap(a, b);
    p[b] = a;
    if (s[a] == s[b]) s[a]++;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges.insert({c, {a, b}});
        edges.insert({c + 1, {a + 1, b}});
    }
    for (int i = 0; i < n; i++) p[i] = i, s[i] = 0;
    ll answer = 0;
    while (!edges.empty())
    {
        int cura = edges.begin()->se.fi % n;
        int curb = edges.begin()->se.se % n;
        int curc = edges.begin()->fi;
        edges.erase(edges.begin());
        if (unite(cura, curb))
        {
            edges.insert({curc + 2, {cura + 1, curb + 1}});
            answer += curc;
        }
    }
    cout << answer << endl;
    return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User KAN
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1440 Byte
Status RE
Exec Time 347 ms
Memory 25984 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:46:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
./Main.cpp:50:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &c);
                                    ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 1300
Status
AC × 3
AC × 6
RE × 27
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 2 ms 256 KB
01-02.txt AC 195 ms 25216 KB
01-03.txt RE 288 ms 25984 KB
01-04.txt RE 108 ms 1024 KB
01-05.txt RE 109 ms 1024 KB
01-06.txt RE 109 ms 1024 KB
01-07.txt RE 109 ms 1024 KB
01-08.txt RE 110 ms 1152 KB
01-09.txt RE 116 ms 2304 KB
01-10.txt RE 195 ms 13568 KB
01-11.txt AC 226 ms 25984 KB
01-12.txt RE 292 ms 25984 KB
01-13.txt RE 293 ms 25984 KB
01-14.txt RE 294 ms 25984 KB
01-15.txt RE 293 ms 25984 KB
01-16.txt RE 293 ms 25984 KB
01-17.txt RE 293 ms 25984 KB
01-18.txt RE 166 ms 1024 KB
01-19.txt RE 110 ms 1024 KB
01-20.txt RE 111 ms 1280 KB
01-21.txt RE 156 ms 8192 KB
01-22.txt RE 299 ms 25984 KB
01-23.txt RE 300 ms 25984 KB
01-24.txt RE 116 ms 2560 KB
01-25.txt RE 344 ms 25984 KB
01-26.txt RE 107 ms 1024 KB
01-27.txt RE 115 ms 2176 KB
01-28.txt RE 239 ms 16384 KB
01-29.txt RE 347 ms 25984 KB
01-30.txt RE 330 ms 25984 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 2 ms 256 KB
sample-03.txt AC 2 ms 256 KB