Submission #994201
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))
// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD
// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;
int data[252521];
int init(){
REP(i,252521)data[i]=-1;
}
int root(int x){
return data[x]<0?x:data[x]=root(data[x]);
}
void unite(int a,int b){
a=root(a);b=root(b);
if(a!=b){
if(data[a]>data[b])swap(a,b);
data[a] += data[b];
data[b] = a;
}
}
int size(int x){
return -data[root(x)];
}
int n,q;
set< pair<ll,pii> > Q;
map<pii,ll> coco;
void addd(pii x,ll c){
if(coco.count(x)){
if(coco[x] <= c){
return;
}else{
Q.erase(Q.find(make_pair(coco[x],x)));
}
}
coco[x] = c;
Q.insert(make_pair(c,x));
}
int main(){
scanf("%d%d",&n,&q);
init();
REP(i,q){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addd(pii(a,b),c);
}
ll ans = 0;
while(size(0)!=n){
pair<ll,pii> EE = *Q.begin(); Q.erase(Q.begin());
ll c = EE.first;
int a = EE.second.first;
int b = EE.second.second;
if(root(a)!=root(b)){
unite(a,b);
ans += c;
}
a++;
if(a==n)a=0;
addd(pii(b,a),c+1ll);
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time
2016-11-26 14:41:42+0900
Task
G - Zigzag MST
User
rickytheta
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1930 Byte
Status
TLE
Exec Time
2111 ms
Memory
134016 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:69:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
^
./Main.cpp:73:29: 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
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
4 ms
1280 KB
01-02.txt
AC
52 ms
1280 KB
01-03.txt
AC
995 ms
84352 KB
01-04.txt
AC
185 ms
16896 KB
01-05.txt
AC
277 ms
28416 KB
01-06.txt
AC
307 ms
30208 KB
01-07.txt
AC
378 ms
38656 KB
01-08.txt
AC
1170 ms
82688 KB
01-09.txt
AC
1397 ms
86784 KB
01-10.txt
TLE
2111 ms
132608 KB
01-11.txt
AC
1037 ms
69248 KB
01-12.txt
TLE
2097 ms
122240 KB
01-13.txt
TLE
2111 ms
134016 KB
01-14.txt
TLE
2111 ms
133888 KB
01-15.txt
TLE
2111 ms
133248 KB
01-16.txt
TLE
2089 ms
123136 KB
01-17.txt
TLE
2111 ms
131072 KB
01-18.txt
AC
343 ms
26240 KB
01-19.txt
AC
362 ms
37248 KB
01-20.txt
AC
1536 ms
92928 KB
01-21.txt
TLE
2110 ms
111104 KB
01-22.txt
TLE
2110 ms
109184 KB
01-23.txt
TLE
2109 ms
106496 KB
01-24.txt
AC
293 ms
26240 KB
01-25.txt
AC
421 ms
26240 KB
01-26.txt
AC
225 ms
26240 KB
01-27.txt
TLE
2110 ms
121344 KB
01-28.txt
TLE
2109 ms
107008 KB
01-29.txt
TLE
2109 ms
106240 KB
01-30.txt
TLE
2109 ms
106240 KB
sample-01.txt
AC
4 ms
1280 KB
sample-02.txt
AC
4 ms
1280 KB
sample-03.txt
AC
4 ms
1280 KB