Submission #1108796
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}
typedef tuple<LL,int,int> T;
typedef pair<int,int> P;
#define fi first
#define se second
int N,Q;
map<int,int> rg;
priority_queue<T,vector<T>,greater<T>> que;
T abc[212345];
int used[212345];
bool in_range(LL a){
auto nxt=rg.lower_bound(a);
return (nxt!=rg.end()&&nxt->se<=a);
}
int add_range(LL a){
if(in_range(a))return 0;
auto nxt=rg.lower_bound(a);
if(nxt!=rg.end()&&nxt->se==a+1){
//a-1] a [a+1
if(rg.count(a-1)==1){
int bg=rg[a-1];
int ed=nxt->fi;
rg.erase(a-1);
rg[ed]=bg;
}
//null a [a+1
else{
int bg=a;
int ed=nxt->fi;
rg[ed]=bg;
}
}
else{
//a-1] a null
if(rg.count(a-1)==1){
int bg=rg[a-1];
int ed=a;
rg.erase(a-1);
rg[ed]=bg;
}
//null a null
else{
int bg=a;
int ed=a;
rg[ed]=bg;
}
}
return 1;
}
LL get_nxt(int &a,int &b){
LL prev_a=a;
LL prev_b=b;
LL na=rg.lower_bound(a)->fi+1;
LL nb=rg.lower_bound(b)->fi+1;
LL cost;
if(na-a>=nb-b){
na=a+(nb-b-1);
cost=na-a+nb-b;
b=na%N;
a=nb%N;
}
else{
nb=b+(na-a);
cost=na-a+nb-b;
b=nb%N;
a=na%N;
}
return cost;
}
int main(){
scanf("%d %d",&N,&Q);
vector<vector<int>> g(N);
int rest=N;
LL res=0;
REP(i,Q){
int a,b;LL c;
scanf("%d %d %lld",&b,&a,&c);
if(a==b){
int tmp=a;
a=(b+1)%N,c++;b=tmp;
}
abc[i]=T(c,a,b);
g[a].push_back(i);
g[b].push_back(i);
}
REP(i,Q)used[i]=0;
//init
{
int id=0;
REP(i,Q)
if(abc[i]<abc[id])
id=i;
int a,b;LL c;
tie(c,a,b)=abc[id];
rest-=add_range(a);add_range(a+N);
rest-=add_range(b);add_range(b+N);
res+=c;
while(g[a].size()){
if(!used[g[a].back()]){
que.push(abc[g[a].back()]);
}
used[g[a].back()]=1;
g[a].pop_back();
}
while(g[b].size()){
if(!used[g[b].back()]){
que.push(abc[g[b].back()]);
}
used[g[b].back()]=1;
g[b].pop_back();
}
}
while(rest){
auto top=que.top();que.pop();
int a,b;LL c;
tie(c,a,b)=top;
//cout<<a<<" "<<b<<" "<<c<<endl;
if(!in_range(a)){
// cout<<a<<" "<<b<<" "<<c<<endl;
res+=c;
rest-=add_range(a);add_range(a+N);
while(g[a].size()){
if(!used[g[a].back()]){
que.push(abc[g[a].back()]);
}
used[g[a].back()]=1;
g[a].pop_back();
}
}
else if(!in_range(b)){
//cout<<a<<" "<<b<<" "<<c<<endl;
res+=c;
rest-=add_range(b);add_range(b+N);
while(g[b].size()){
if(!used[g[b].back()]){
que.push(abc[g[b].back()]);
}
used[g[b].back()]=1;
g[b].pop_back();
}
}
c+=get_nxt(a,b);
que.push(T(c,a,b));
}
cout<<res<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
btk15049 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3854 Byte |
Status |
WA |
Exec Time |
2103 ms |
Memory |
22768 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:87:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&Q);
^
./Main.cpp:93:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %lld",&b,&a,&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 |
3 ms |
256 KB |
01-02.txt |
AC |
74 ms |
9896 KB |
01-03.txt |
WA |
202 ms |
18676 KB |
01-04.txt |
AC |
51 ms |
4992 KB |
01-05.txt |
AC |
48 ms |
4992 KB |
01-06.txt |
AC |
55 ms |
4992 KB |
01-07.txt |
WA |
61 ms |
4992 KB |
01-08.txt |
WA |
69 ms |
4992 KB |
01-09.txt |
WA |
119 ms |
6144 KB |
01-10.txt |
WA |
200 ms |
13044 KB |
01-11.txt |
WA |
194 ms |
14960 KB |
01-12.txt |
WA |
275 ms |
18548 KB |
01-13.txt |
WA |
261 ms |
18676 KB |
01-14.txt |
WA |
275 ms |
18676 KB |
01-15.txt |
WA |
275 ms |
18676 KB |
01-16.txt |
WA |
267 ms |
18676 KB |
01-17.txt |
WA |
267 ms |
18676 KB |
01-18.txt |
TLE |
2103 ms |
14568 KB |
01-19.txt |
WA |
56 ms |
4992 KB |
01-20.txt |
WA |
152 ms |
5248 KB |
01-21.txt |
WA |
423 ms |
12024 KB |
01-22.txt |
WA |
631 ms |
22768 KB |
01-23.txt |
WA |
645 ms |
22768 KB |
01-24.txt |
TLE |
2102 ms |
5760 KB |
01-25.txt |
TLE |
2103 ms |
15360 KB |
01-26.txt |
AC |
58 ms |
4992 KB |
01-27.txt |
WA |
192 ms |
6400 KB |
01-28.txt |
WA |
814 ms |
13808 KB |
01-29.txt |
WA |
1076 ms |
15344 KB |
01-30.txt |
WA |
1240 ms |
18800 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
2 ms |
256 KB |
sample-03.txt |
AC |
2 ms |
256 KB |