Submission #993042
Source Code Expand
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }
template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
int c=0;
while ( *s!=',' || c!=0 ) {
if ( *s=='(' || *s=='[' || *s=='{' ) c++;
if ( *s==')' || *s==']' || *s=='}' ) c--;
cerr<<*s++;
}
cerr<<"="<<head<<", ";
_dump(s+1,tail...);
}
#define dump(...) do { \
fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
_dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)
template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
s<<"[";
for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
s<<"]";
return s;
}
template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif
template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }
void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
_R(head);
R(tail...);
}
template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
if ( i!=x.cbegin() ) putchar(' ');
_W(*i);
}
}
void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
_W(head);
putchar(sizeof...(tail)?' ':'\n');
W(tail...);
}
#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
freopen(name ".in","r",stdin); \
freopen(name ".out","w",stdout); \
} while (0)
#endif
// }}}
struct DJS {
vector<int> fa,sz;
void init( int n ) {
n++; // be nice for 1-index usage
fa.resize(n);
sz.resize(n);
for ( int i=0; i<n; i++ ) sz[fa[i]=i]=1;
}
int f( int x ) {
return x==fa[x]?x:fa[x]=f(fa[x]);
}
void u( int a, int b ) {
a=f(a); b=f(b);
if ( a==b ) return;
if ( sz[a]>sz[b] ) swap(a,b);
fa[a]=b;
sz[b]+=sz[a];
}
} djs;
const int M=2e5+10;
int n,m;
struct E {
int a,b,c,t;
void next() {
swap(a,b);
b++;
if ( b==n ) b=0;
c++;
}
} e[M];
priority_queue<PII,vector<PII>,greater<PII>> q;
void push( int id ) {
q.push({e[id].c,id});
}
int main() {
R(n,m);
REP(i,m) R(e[i].a,e[i].b,e[i].c);
djs.init(n);
REP(i,m) push(i);
LL ans=0;
while ( !q.empty() ) {
int id=q.top().second;
q.pop();
if ( djs.f(e[id].a)!=djs.f(e[id].b) ) {
djs.u(e[id].a,e[id].b);
ans+=e[id].c;
e[id].t=0;
} else {
e[id].t++;
}
e[id].next();
if ( e[id].t<=10 ) push(id);
}
W(ans);
return 0;
}
Submission Info
Submission Time
2016-11-26 13:31:43+0900
Task
G - Zigzag MST
User
shik
Language
C++14 (GCC 5.4.1)
Score
1300
Code Size
4076 Byte
Status
AC
Exec Time
366 ms
Memory
7156 KB
Compile Error
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
void _R( long long &x ) { scanf("%" PRId64,&x); }
^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void _R( int &x ) { scanf("%d",&x); }
^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void _R( long long &x ) { scanf("%" PRId64,&x); }
^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...
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
291 ms
5492 KB
01-03.txt
AC
311 ms
7156 KB
01-04.txt
AC
11 ms
1792 KB
01-05.txt
AC
13 ms
1792 KB
01-06.txt
AC
14 ms
1792 KB
01-07.txt
AC
15 ms
1792 KB
01-08.txt
AC
22 ms
1792 KB
01-09.txt
AC
45 ms
2176 KB
01-10.txt
AC
186 ms
4472 KB
01-11.txt
AC
305 ms
6388 KB
01-12.txt
AC
340 ms
7156 KB
01-13.txt
AC
341 ms
7156 KB
01-14.txt
AC
339 ms
7156 KB
01-15.txt
AC
343 ms
7156 KB
01-16.txt
AC
342 ms
7156 KB
01-17.txt
AC
339 ms
7156 KB
01-18.txt
AC
269 ms
7156 KB
01-19.txt
AC
13 ms
1792 KB
01-20.txt
AC
38 ms
1920 KB
01-21.txt
AC
119 ms
3324 KB
01-22.txt
AC
317 ms
7156 KB
01-23.txt
AC
318 ms
7156 KB
01-24.txt
AC
28 ms
2176 KB
01-25.txt
AC
289 ms
7156 KB
01-26.txt
AC
14 ms
1792 KB
01-27.txt
AC
41 ms
2176 KB
01-28.txt
AC
231 ms
4856 KB
01-29.txt
AC
349 ms
6388 KB
01-30.txt
AC
366 ms
7156 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