Submission #1049357
Source Code Expand
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<iostream>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define For(i,x,y) for(int i=((int)x);i<=((int)y);i++)
#define Dep(i,y,x) for(int i=((int)y);i>=((int)x);i--)
#define Rep(i,x) for (int y,i=head[x];i;i=E[i].nxt)
using namespace std;
const int N=200005;
const int inf=1000000009;
typedef double db;
typedef long long ll;
typedef unsigned int uint;
typedef pair<int,int> pii;
/*inline int rd() {
char c=getchar(); int t=0,f=1;
while (c<48) c=getchar();
while (c>47) t=(t<<1)+(t<<3)+c-48,c=getchar(); return t*f;
}*/
char Buf[30000000],*c=Buf;
inline int rd() {
int t=0;
while (*c<48) c++;
while (*c>47) t=(t<<1)+(t<<3)+*c-48,c++; return t;
}
void wt(int x) {
if (x<0) putchar('-'),wt(-x);
else { if (x>9) wt(x/10); putchar(x%10+48); }
}
struct Data {
int A,B,val,k;
bool operator>(Data P)const {
return val>P.val;
}
}TP,tmp;
struct Priority_Queue {
int size;
Data Heap[N<<1];
Data top() { return Heap[1]; }
inline void down() {
int x=1,k=1;
while (1) {
if ((x<<1)<=size && Heap[k]>Heap[x<<1]) k=x<<1;
if ((x<<1|1)<=size && Heap[k]>Heap[x<<1|1]) k=x<<1|1;
if (x==k) return; swap(Heap[x],Heap[k]); x=k;
}
}
inline void up(int x) {
while (x>1) {
if (Heap[x>>1]>Heap[x])
swap(Heap[x>>1],Heap[x]),x>>=1;
else return;
}
}
inline void pop() { swap(Heap[1],Heap[size--]); down(); }
inline void push(Data P) { Heap[++size]=P; up(size); }
}Q;
struct Hash_Table {
bool key[60000007][2];
inline int f(Data P) { return (1ll*P.A*500009%60000007+P.B)%60000007; }
inline void ins(Data P) { key[f(P)][P.k]=1; swap(P.A,P.B),P.k^=1; key[f(P)][P.k]=1; return; }
inline bool find(Data P) { if (key[f(P)][P.k]) return 1; swap(P.A,P.B),P.k^=1; return key[f(P)][P.k]; }
}Hash;
//priority_queue<Data>Q;
int n,m,fa[N],key; ll Ans;
//map<pair<pii,int>,bool>Map;
inline int get(int x) { return fa[x]==x?x:fa[x]=get(fa[x]); }
inline void inc(Data &P) {
if (P.k==0) P.k=1,P.A++;
else P.k=0,P.B++; P.val++;
if (P.A==n) P.A=0;
if (P.B==n) P.B=0; return;
}
int main() {
fread(Buf,1,29999999,stdin);
n=rd(),m=rd(); int cnt=0; tmp.k=0;
For (i,1,m) {
tmp.A=rd(),tmp.B=rd(),tmp.val=rd();
Q.push(tmp);
}
For (i,0,n-1) fa[i]=i;
while (Q.size) {
if (key==n-1) break;
TP=Q.top(),Q.pop();
cnt++;
// if (Map.find(mp(mp(TP.A,TP.B),TP.k))!=Map.end()) continue; else Map[mp(mp(TP.A,TP.B),TP.k)]=1;
// if (Map.find(mp(mp(TP.B,TP.A),TP.k^1))!=Map.end()) continue; else Map[mp(mp(TP.B,TP.A),TP.k^1)]=1;
if (Hash.find(TP)) continue; else Hash.ins(TP);
if (get(TP.A)!=get(TP.B)) {
Ans+=TP.val,key++;
fa[get(TP.A)]=get(TP.B);
}
// else continue;
inc(TP),Q.push(TP);
}
cout<<Ans<<endl;
// printf("%d\n",cnt);
return 0;
}
/*
7 1
5 2 1
*/
Submission Info
Submission Time
2016-12-31 15:16:38+0900
Task
G - Zigzag MST
User
rxdoi
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
3064 Byte
Status
WA
Exec Time
2114 ms
Memory
125824 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:99:29: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
fread(Buf,1,29999999,stdin);
^
Judge Result
Set Name
sample
all
Score / Max Score
0 / 0
0 / 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
13 ms
6144 KB
01-03.txt
AC
401 ms
125824 KB
01-04.txt
AC
234 ms
118912 KB
01-05.txt
AC
258 ms
118528 KB
01-06.txt
AC
268 ms
118400 KB
01-07.txt
AC
285 ms
118272 KB
01-08.txt
AC
388 ms
118272 KB
01-09.txt
WA
451 ms
118656 KB
01-10.txt
WA
568 ms
121984 KB
01-11.txt
WA
353 ms
125184 KB
01-12.txt
WA
508 ms
125824 KB
01-13.txt
WA
657 ms
125824 KB
01-14.txt
WA
604 ms
125824 KB
01-15.txt
WA
537 ms
125824 KB
01-16.txt
WA
511 ms
125824 KB
01-17.txt
WA
531 ms
125824 KB
01-18.txt
AC
250 ms
125824 KB
01-19.txt
AC
278 ms
118272 KB
01-20.txt
WA
609 ms
118272 KB
01-21.txt
WA
651 ms
119936 KB
01-22.txt
WA
665 ms
124288 KB
01-23.txt
WA
785 ms
124288 KB
01-24.txt
AC
241 ms
118656 KB
01-25.txt
AC
326 ms
125824 KB
01-26.txt
AC
243 ms
118272 KB
01-27.txt
TLE
2114 ms
118528 KB
01-28.txt
TLE
2114 ms
123008 KB
01-29.txt
TLE
2114 ms
125312 KB
01-30.txt
TLE
2114 ms
125824 KB
sample-01.txt
AC
3 ms
256 KB
sample-02.txt
AC
2 ms
256 KB
sample-03.txt
AC
3 ms
256 KB