#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define Pii pair< pii , pii >
#define int long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 6e5 + 10 , sq = 3 , maxq = 1e7 + 1 , inf = 1e18 + 10 , mod= 998244353 ,lg = 20 ;
vector <pair <pii , int> > ed ;
vector <int> vec[maxn] ;
int pr[maxn] , n , m ;
int ch(int val){
for(int i = 0 ; i < n ; i++){
pr[i] = 0 ;
}
for(int i =0 ; i < ed.size() ; i++){
pr[ed[i].F.F]+= ed[i].S ;
pr[ed[i].F.S]-= ed[i].S ;
}
priority_queue <pair <int ,pii> > pq ;
int w = 0 , ans = 0 ;
for(int i = 0 ; i < n ; i++){
if(i)pr[i] += pr[i-1] ;
for(int j = 0 ; j < vec[i].size() ; j++){
pq.push({ed[vec[i][j]].F.S , {vec[i][j] , ed[vec[i][j]].S}});
}
while(pr[i] > val){
int v = pq.top().S.F , ted = pq.top().S.S; ;
pq.pop() ;
if(ed[v].F.S < i)continue ;
if(pr[i]-2*ted > val){
pr[i]-=2*ted;
pr[ed[v].F.S]+= 2*ted ;
ans += ted;
}else{
int gp = (pr[i] - val + 1)/2 ;
pr[i] -= 2*gp ;
pr[ed[v].F.S]+= 2*gp ;
ans += gp ;
pq.push({ed[v].F.S , {v , ted-gp}}) ;
}
}
}
return ans ;
}
signed main() {
ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
cin >> n >> m ;
for(int i =1 ; i <= m ; i++){
int a , b , c;
cin >> a >> b >> c ;
a--;
b--;
pr[a]++;
pr[b]--;
ed.pb({{a, b} , c}) ;
}
for(int i = 1; i< n ;i++){
pr[i]+= pr[i-1] ;
}
int mx= 0 ;
for(int i = 0 ; i < n ; i++){
if(pr[i] > pr[mx])mx = i ;
}
for(int i =0 ; i < ed.size() ; i++){
ed[i].F.F = (ed[i].F.F - mx+ n)%n ;
ed[i].F.S = (ed[i].F.S - mx + n)%n ;
if(ed[i].F.F > ed[i].F.S)swap(ed[i].F.F , ed[i].F.S);
vec[ed[i].F.F].pb(i) ;
}
cout << min(ch(0) , ch(1)+1) << "\n" ;
}
/*
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14784 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
4 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14936 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
3 ms |
14788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14784 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
4 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14936 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
3 ms |
14788 KB |
Output is correct |
16 |
Correct |
4 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14936 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
4 ms |
14940 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14784 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
4 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14936 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
3 ms |
14788 KB |
Output is correct |
16 |
Correct |
4 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14936 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
4 ms |
14940 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
28 |
Correct |
4 ms |
15196 KB |
Output is correct |
29 |
Incorrect |
4 ms |
15196 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14784 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
4 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14936 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
3 ms |
14788 KB |
Output is correct |
16 |
Correct |
4 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14936 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
4 ms |
14940 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
28 |
Correct |
4 ms |
15196 KB |
Output is correct |
29 |
Incorrect |
4 ms |
15196 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14784 KB |
Output is correct |
3 |
Correct |
3 ms |
14940 KB |
Output is correct |
4 |
Correct |
4 ms |
14940 KB |
Output is correct |
5 |
Correct |
3 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14936 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
3 ms |
14788 KB |
Output is correct |
16 |
Correct |
4 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14936 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
4 ms |
14940 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
28 |
Correct |
4 ms |
15196 KB |
Output is correct |
29 |
Incorrect |
4 ms |
15196 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |