QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420793#892. Minimal CutCharlieVinnieRE 88ms640516kbC++206.5kb2024-05-24 22:00:332024-05-24 22:00:36

Judging History

你现在查看的是最新测评结果

  • [2024-05-24 22:00:36]
  • 评测
  • 测评结果:RE
  • 用时:88ms
  • 内存:640516kb
  • [2024-05-24 22:00:33]
  • 提交

answer

// #define _GLIBCXX_DEBUG
#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](){}()
#define debuga(...) [](){}()
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define fi first
#define se second
using namespace std; typedef long long ll;
constexpr int N=1e6+5,M=2e7+5; using pii = pair<int,int>;
#define k1 (k<<1)
#define k2 (k<<1|1)
struct Tag{
    pii mn; int cur;
    Tag() { mn.fi=1e9; }
    Tag(const pii& A,const int& B) { mn=A; cur=B; }
    friend Tag operator* (const Tag& A,const Tag& B){
        Tag res;
        res.mn=min(A.mn,pii(A.cur+B.mn.fi,B.mn.se));
        res.cur=A.cur+B.cur;
        return res;
    }
    static Tag TagAdd(int x) { return Tag(pii(1e9,0),x); }
    static Tag TagRec(int t) { return Tag{pii(0,t),0}; }
};
struct Data{
    pair<int,pii> mn; pii cur;
    Data() { mn.fi=1e9; mn.se=cur=pii(0,0); }
    Data(const pair<int,pii>& A,const pii& B) { mn=A; cur=B; }
    Data& operator*= (const Tag& tag){
        mn=min(mn,make_pair(cur.fi+tag.mn.fi,pii(tag.mn.se,cur.se)));
        cur.fi+=tag.cur;
        return *this;
    }
    friend Data operator+ (const Data& A,const Data& B) { return Data(min(A.mn,B.mn),min(A.cur,B.cur)); }
};
class STree{
    int n,tot,lc[M],rc[M]; Data O[M]; Tag tag[M]; bool vis[M];
    int Copy(int k) { tot++; assert(tot<M); lc[tot]=lc[k]; rc[tot]=rc[k]; O[tot]=O[k]; tag[tot]=tag[k]; vis[tot]=vis[k]; return tot; }
    void setg(int k,Tag t) { O[k]*=t; tag[k]=tag[k]*t; vis[k]=1; }
    void pushdown(int k) { setg(lc[k],tag[k]); setg(rc[k],tag[k]); tag[k]=Tag{}; vis[k]=0; }
    void update(int k) { O[k]=O[lc[k]]+O[rc[k]]; }
    void build(int k,int l,int r){
        if(l==r) return O[k].cur.se=l,void();
        int mid=(l+r)>>1; build(lc[k]=++tot,l,mid); build(rc[k]=++tot,mid+1,r); update(k);
    }
    int add(int k,int l,int r,int ql,int qr,int x){
        int p=Copy(k); if(ql<=l&&r<=qr) return setg(p,Tag::TagAdd(x)),p;
        int mid=(l+r)>>1; assert(lc[k]&&rc[k]);
        if(vis[p]) { lc[p]=Copy(lc[k]); rc[p]=Copy(rc[k]); pushdown(p); }
        if(ql<=mid) lc[p]=add(lc[p],l,mid,ql,qr,x);
        if(mid+1<=qr) rc[p]=add(rc[p],mid+1,r,ql,qr,x);
        update(p); return p;
    }
    pair<int,pii> query(int k,int l,int r,int ql,int qr,Tag t){
        if(ql<=l&&r<=qr) { Data res=O[k]; res*=t; return res.mn; }
        int mid=(l+r)>>1; pair<int,pii> res(1e9,{0,0}); t=tag[k]*t;
        if(ql<=mid) res=min(res,query(lc[k],l,mid,ql,qr,t));
        if(mid+1<=qr) res=min(res,query(rc[k],mid+1,r,ql,qr,t));
        return res;
    }
public:
    void init(int _n) { n=_n; tot++; build(1,1,n); }
    int add(int k,int l,int r,int x) { return add(k,1,n,l,r,x); }
    int record(int k,int t) { int p=Copy(k); setg(p,Tag::TagRec(t)); return p; }
    pair<int,pii> query(int k,int l,int r) { auto res=query(k,1,n,l,r,Tag{}); assert(res.fi!=1e9); assert(res.fi>=0); return res; }
    int TOT() { return tot; }
}T;
int n,m,rt[20][N]; struct TREE { int x,y,z; } TR[N]; int Tcnt;
struct Rect { int x1,x2,y1,y2,z; }; vector<Rect> lis[N<<2];
void Add(int k,int l,int r,int x1,int x2,int y1,int y2,int z){
    lis[k].push_back(Rect{max(x1,l),min(x2,r),y1,y2,z}); if(x1<=l&&r<=x2) return;
    int mid=(l+r)>>1;
    if(x1<=mid) Add(k1,l,mid,x1,x2,y1,y2,z);
    if(mid+1<=x2) Add(k2,mid+1,r,x1,x2,y1,y2,z);
}
void Add(int x1,int x2,int y1,int y2,int z){
    // For(i,x1,x2) For(j,y1,y2) a[i][j]+=z;
    if(x1>x2||y1>y2) return;
    Add(1,1,n,x1,x2,y1,y2,z);
}
void build(int k,int l,int r,int d,int o){
    static vector<tuple<int,int,int>> oper[N];
    int mid=(l+r)>>1; For(i,l,r) oper[i].clear();
    int qwq=o;
    for(auto [x1,x2,y1,y2,z]:lis[k]){
        if(x1<=mid&&mid+1<=x2){
            qwq=T.add(qwq,y1,y2,z);
            oper[x1-1].emplace_back(y1,y2,-z);
            oper[x2+1].emplace_back(y1,y2,-z);
        }
        else if(x2<=mid){
            oper[x2].emplace_back(y1,y2,z);
            oper[x1-1].emplace_back(y1,y2,-z);
        }
        else{ assert(mid+1<=x1);
            oper[x1].emplace_back(y1,y2,z);
            oper[x2+1].emplace_back(y1,y2,-z);
        }
    }
    int oo=qwq;
    Rev(i,mid,l){
        for(auto [y1,y2,z]:oper[i]) oo=T.add(oo,y1,y2,z);
        rt[d][i]=oo=T.record(oo,i);
    }
    oo=qwq;
    For(i,mid+1,r){
        for(auto [y1,y2,z]:oper[i]) oo=T.add(oo,y1,y2,z);
        rt[d][i]=oo=T.record(oo,i);
    }
    if(l==r) return;
    oo=o; for(auto [x1,x2,y1,y2,z]:lis[k]) if(x1==l&&x2==r) oo=T.add(oo,y1,y2,z);
    build(k1,l,mid,d+1,oo); build(k2,mid+1,r,d+1,oo);
}
pair<int,pii> query(int k,int l,int r,int d,int ql,int qr,int y1,int y2){
    if(l==r) return T.query(rt[d][l],y1,y2);
    int mid=(l+r)>>1;
    if(ql<=mid&&mid+1<=qr) return min(T.query(rt[d][ql],y1,y2),T.query(rt[d][qr],y1,y2));
    else if(qr<=mid) return query(k1,l,mid,d+1,ql,qr,y1,y2);
    else return assert(mid+1<=ql),query(k2,mid+1,r,d+1,ql,qr,y1,y2);
}
pair<int,pii> query(int x1,int x2,int y1,int y2){
    return query(1,1,n,1,x1,x2,y1,y2);
}
void solve(int l,int r){
    if(l==r) return;
    auto qwq=query(l,r-1,r,n);
    if(l!=1) qwq=min(qwq,query(1,l-1,l,r-1));
    auto [x,y]=qwq.se;
    if(l<=y&&y<r) swap(x,y);
    assert(l<=x&&x<r);
    TR[++Tcnt]=TREE{l,r,qwq.fi};
    solve(l,x); solve(x+1,r);
}
signed main(){
    // Fin("data.in");
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    For(_,1,m){
        int x,y,z; cin>>x>>y>>z; if(x>y) swap(x,y);
        if(x>1) Add(1,x-1,x,y-1,z);
        Add(x,y-1,y,n,z);
    }
    // STree::init(n); T[++QWQ].__reset(); build(1,1,n,1,QWQ);
    T.init(n); build(1,1,n,1,1);
    solve(1,n); assert(Tcnt==n-1); sort(TR+1,TR+n,[](TREE X,TREE Y){return X.z>Y.z;});
    static int fa[N],siz[N]; iota(fa+1,fa+1+n,1); For(i,1,n) siz[i]=1;
    function<int(int)> getfa=[&](int x) { return x==fa[x]?x:(fa[x]=getfa(fa[x])); };
    int ans=0; constexpr int mod=998244353;
    For(i,1,n-1){
        auto [x,y,z]=TR[i]; x=getfa(x); y=getfa(y);
        ans=(ans+1ll*siz[x]*siz[y]%mod*z)%mod; fa[y]=x; siz[x]+=siz[y];
    }
    debug(ans);
    cout<<(ans+1ll*n*(n-1)/2%mod*ll(2e9))%mod<<'\n';
    debug(T.TOT());
    return 0;
}

// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING

// Started Coding On: May 24 Fri, 16 : 06 : 47

詳細信息

Test #1:

score: 100
Accepted
time: 31ms
memory: 629532kb

input:

4 2
1 3 2
2 4 2

output:

21067776

result:

ok "21067776"

Test #2:

score: 0
Accepted
time: 59ms
memory: 630092kb

input:

79 190
24 30 8372
16 17 3623
47 43 577
47 45 10000
50 49 9644
35 25 882
23 24 1994
54 55 7778
32 33 230
52 53 6078
5 10 8214
25 26 6829
21 22 340
67 68 6066
10 1 8104
9 10 3085
44 43 5659
33 34 5505
7 10 337
12 13 3804
5 1 4735
25 28 6650
61 60 9290
14 6 9857
38 35 6228
48 49 3076
60 59 4972
54 52 4...

output:

844859152

result:

ok "844859152"

Test #3:

score: 0
Accepted
time: 23ms
memory: 631488kb

input:

71 199
20 19 869
46 61 9375
62 52 877
32 31 267
41 63 678
25 23 1224
61 62 103
28 29 4640
51 52 2086
47 49 5163
27 28 3198
9 8 5530
68 69 5035
26 28 7214
36 40 8779
11 12 2949
10 11 5381
1 71 1450
23 24 4741
33 32 6857
6 9 8673
34 39 6459
32 33 1827
14 13 8042
5 6 51
70 6 146
21 22 276
20 17 5504
18...

output:

746051489

result:

ok "746051489"

Test #4:

score: 0
Accepted
time: 19ms
memory: 630964kb

input:

78 190
54 66 589
64 65 9958
71 72 2115
77 73 5248
54 58 5868
68 57 72
56 60 1476
1 77 7739
16 17 9093
60 59 5315
20 14 313
6 59 277
60 64 3132
75 72 455
63 64 6752
30 38 4810
71 76 2424
30 31 8090
71 73 6643
26 27 3489
4 60 315
62 63 8501
38 39 7761
61 59 2258
46 47 5454
17 18 972
59 55 333
69 56 73...

output:

582293834

result:

ok "582293834"

Test #5:

score: 0
Accepted
time: 47ms
memory: 631192kb

input:

74 198
10 11 767
25 26 4090
46 42 1653
2 5 3333
43 38 7106
53 52 6205
4 2 529
20 27 3335
49 52 2604
21 15 5265
28 29 949
8 7 4439
55 56 99
7 8 238
66 69 7812
17 29 1364
39 47 1270
9 8 5229
5 4 3465
43 42 7064
30 31 7767
25 32 5244
30 31 7196
7 9 3118
56 57 5779
43 39 9187
51 50 5735
16 12 7606
40 41...

output:

508442899

result:

ok "508442899"

Test #6:

score: 0
Accepted
time: 60ms
memory: 631208kb

input:

78 192
21 22 4125
3 4 3230
71 72 4489
76 77 8868
55 56 7672
17 18 5081
30 29 1254
18 19 3896
39 32 8008
7 8 7118
70 71 3546
47 39 994
12 13 4972
77 78 123
12 13 1701
8 7 1029
63 1 478
31 28 4211
5 6 8249
77 74 4092
73 74 795
51 52 6818
5 6 8430
9 10 7953
14 15 8539
45 46 3682
11 9 9308
15 17 2643
12...

output:

568925767

result:

ok "568925767"

Test #7:

score: 0
Accepted
time: 36ms
memory: 630668kb

input:

71 192
44 28 4637
45 27 8128
61 11 4055
3 69 777
71 1 7158
9 63 5849
55 17 1415
42 30 1583
17 55 7200
12 60 5049
42 30 2190
14 58 9752
40 32 2155
22 50 2608
55 17 422
64 8 6165
27 45 4354
48 24 2506
67 5 6327
45 27 4340
56 16 6535
6 66 5083
47 25 7297
33 39 1273
23 49 8104
12 60 8773
62 10 472
70 2 ...

output:

740575153

result:

ok "740575153"

Test #8:

score: 0
Accepted
time: 39ms
memory: 630472kb

input:

74 196
19 56 2208
20 55 5639
58 17 5675
68 7 3559
10 65 873
25 50 193
50 25 6346
54 21 931
56 19 6211
59 16 6563
7 68 7976
35 40 7101
67 8 2437
53 22 7139
7 68 8435
9 66 464
57 18 9881
18 57 1338
57 18 3184
2 73 7381
34 41 5615
36 39 3187
58 17 2430
66 9 7393
55 20 1222
41 34 1139
68 7 5408
39 36 16...

output:

500821698

result:

ok "500821698"

Test #9:

score: 0
Accepted
time: 43ms
memory: 630116kb

input:

77 192
15 55 74
46 5 1414
67 68 4865
8 25 3974
41 31 2480
42 63 3038
22 77 1372
37 17 1208
50 17 2197
58 68 669
1 22 1878
11 49 1465
74 2 3145
11 20 4555
42 25 979
50 49 7595
71 16 2859
13 77 4927
31 21 2599
21 23 1947
28 25 7614
28 58 1171
72 49 1826
70 58 731
48 74 2202
60 72 2635
52 27 1781
34 2 ...

output:

319693148

result:

ok "319693148"

Test #10:

score: 0
Accepted
time: 39ms
memory: 630416kb

input:

76 190
50 34 4806
62 10 2548
45 34 2023
21 28 189
17 49 2411
50 39 3689
28 11 2519
59 32 2598
72 64 8754
31 56 1325
57 58 3376
47 46 6921
28 61 752
75 35 1452
9 33 1213
63 19 208
42 73 1115
22 40 929
59 53 1063
46 51 5736
35 15 994
22 23 5109
49 21 428
12 58 494
47 74 2423
1 5 8528
29 75 2183
43 6 1...

output:

50667227

result:

ok "50667227"

Test #11:

score: 0
Accepted
time: 52ms
memory: 629792kb

input:

71 196
12 37 1395
29 70 684
3 38 855
37 36 2708
69 37 1550
47 52 9602
19 45 1957
14 9 7724
63 52 1541
18 14 8279
64 50 2595
33 69 1303
33 57 989
12 17 4600
50 64 3908
60 29 468
15 24 1803
64 39 1795
34 42 2170
28 23 1308
33 45 428
16 20 131
28 8 1027
42 49 1658
48 53 772
69 23 509
69 50 3253
9 42 16...

output:

765565056

result:

ok "765565056"

Test #12:

score: 0
Accepted
time: 60ms
memory: 635064kb

input:

293 993
140 142 9682
232 243 313
67 68 5028
130 129 5855
36 35 8091
96 95 2322
68 67 2355
176 175 4817
242 238 5923
213 211 2343
278 277 6300
281 283 596
269 265 642
160 165 1585
274 275 2148
224 225 9745
99 98 680
130 127 4692
224 222 7351
270 271 5653
140 142 5254
219 217 7041
204 203 1154
263 266...

output:

487446357

result:

ok "487446357"

Test #13:

score: 0
Accepted
time: 79ms
memory: 634444kb

input:

297 993
240 241 6989
266 264 4892
280 281 6358
266 267 5237
88 84 6062
281 286 5497
1 296 3082
49 48 9502
148 149 9732
294 1 4162
176 174 5358
216 217 2924
279 283 61
9 10 681
42 43 2886
43 38 1310
22 24 690
128 129 9666
10 9 7299
26 28 7230
19 21 2030
173 171 8453
34 31 4980
148 149 6886
166 167 33...

output:

635119625

result:

ok "635119625"

Test #14:

score: 0
Accepted
time: 60ms
memory: 634772kb

input:

291 991
205 204 7961
153 148 7043
56 54 3207
130 129 235
47 49 982
7 6 7918
70 74 66
259 260 5461
199 200 4584
271 273 8554
130 128 8487
23 22 7830
269 274 811
94 95 7381
98 99 4011
170 171 8357
83 86 2266
10 9 4076
152 148 2084
143 142 4403
70 71 3178
8 9 6140
110 111 9432
156 157 5593
147 146 2216...

output:

435016731

result:

ok "435016731"

Test #15:

score: 0
Accepted
time: 73ms
memory: 635836kb

input:

294 997
31 27 1334
48 43 9810
40 41 6209
260 270 7098
246 245 3813
246 247 2591
94 87 6194
220 221 1845
94 95 747
33 34 6336
73 67 8120
212 213 5883
127 144 7212
231 239 7259
35 38 767
35 33 4346
92 91 4569
126 127 1683
74 84 7833
89 90 4039
141 106 9006
183 190 9225
100 101 7471
31 34 148
280 282 6...

output:

585062748

result:

ok "585062748"

Test #16:

score: 0
Accepted
time: 67ms
memory: 634664kb

input:

298 992
260 261 8940
229 228 7784
37 38 3250
59 60 3266
43 42 8674
194 195 4921
202 200 941
110 114 5448
225 226 3661
204 205 3635
238 240 896
98 105 867
33 34 5019
13 14 1558
163 159 9152
36 40 8423
226 225 8471
250 251 9567
207 209 6328
77 78 8566
282 283 9587
32 33 2271
62 63 7413
122 123 303
201...

output:

676742353

result:

ok "676742353"

Test #17:

score: 0
Accepted
time: 51ms
memory: 637732kb

input:

291 997
140 152 2769
165 127 7362
191 101 3702
17 275 6461
162 130 7143
52 240 7388
240 52 6220
285 7 5148
286 6 1998
161 131 542
136 156 8621
36 256 6382
287 5 4876
118 174 1539
182 110 5065
149 143 7397
130 162 1150
186 106 8769
22 270 9991
48 244 8800
161 131 3201
46 246 9799
4 288 9053
53 239 74...

output:

423941983

result:

ok "423941983"

Test #18:

score: 0
Accepted
time: 88ms
memory: 639144kb

input:

297 998
80 218 6306
187 111 4494
158 140 5704
122 176 7475
31 267 969
293 5 5388
147 151 1299
289 9 7048
48 250 757
293 5 5914
5 293 223
63 235 6179
188 110 6762
154 144 9141
14 284 355
244 54 8132
46 252 6727
231 67 1171
244 54 6727
32 266 1816
198 100 1956
107 191 7170
112 186 8344
41 257 1620
269...

output:

617769996

result:

ok "617769996"

Test #19:

score: 0
Accepted
time: 67ms
memory: 639372kb

input:

299 994
44 136 381
161 120 1914
267 44 1155
204 232 2751
235 13 163
36 25 4549
195 285 717
188 3 571
72 250 459
106 201 989
92 281 191
37 250 618
183 84 891
137 60 1146
46 135 122
106 205 545
45 22 182
122 238 257
283 98 363
137 215 1056
4 294 3498
73 116 198
96 111 4957
138 29 407
138 7 114
21 154 ...

output:

895803524

result:

ok "895803524"

Test #20:

score: 0
Accepted
time: 51ms
memory: 640516kb

input:

294 991
258 164 932
35 44 3568
284 293 683
160 111 222
274 49 744
165 108 1098
54 106 576
293 168 428
186 219 2100
237 76 135
132 174 175
56 274 1168
190 138 1286
20 218 367
42 74 1586
105 279 181
146 208 391
98 292 140
268 119 387
124 21 198
37 281 1038
112 178 1060
246 168 124
27 229 250
117 280 2...

output:

704435821

result:

ok "704435821"

Test #21:

score: 0
Accepted
time: 76ms
memory: 639016kb

input:

295 997
38 250 335
95 66 3294
23 26 6828
248 116 63
271 120 28
260 160 238
102 118 2914
244 137 765
253 247 5979
40 99 371
249 112 136
193 70 738
287 40 1432
96 227 220
61 20 399
5 42 2190
63 199 235
148 247 532
27 150 680
36 33 163
236 109 613
204 281 1151
286 130 643
225 293 38
153 79 372
11 181 5...

output:

724135682

result:

ok "724135682"

Test #22:

score: -100
Runtime Error

input:

18294 19992
7993 7990 4961
3549 3550 4737
15480 15481 5224
11212 11213 7993
15209 15210 661
13866 13867 5556
15788 15789 9331
7279 7280 260
4084 4085 3153
16816 16817 4944
16503 16504 6105
3542 3543 6081
555 556 5133
7461 7462 446
3027 3028 2409
16493 16494 1055
1511 1512 5530
10259 10260 7165
16503...

output:


result: