oj.uz

Submission #874353

# Submission time Handle Problem Language Result Execution time Memory
874353 2023-11-16T17:40:44 Z winter0101 Reconstruction Project (JOI22_reconstruction) C++14
100 / 100
 704 ms 135504 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=5e2+9;
const int maxm=1e5+9;
const int maxq=1e6+9;
struct edg{
int u,v,w;
bool operator < (const edg &p){
return w<p.w;
}
}a[maxm];
int f[maxn];
int fs(int u){
if (f[u]<0)return u;
return f[u]=fs(f[u]);
}
bool unite(int u,int v){
u=fs(u),v=fs(v);
if (u==v)return 0;
if (f[u]>f[v])swap(u,v);
f[u]+=f[v];
f[v]=u;
return 1;
}
long long b[maxq];
int l1[maxm],r1[maxm];
vector<int>add[maxq][2];
vector<int>del[maxq][2];
/*voi moi i tim r[i] sao cho unite tu i+1 den r[i] thi se k can unite i
=> khoang can dung khi w[i]<=query se co the la i den r[i]
nhan xet voi moi query thuoc khoang w[i] den w[r[i]] thi goi x la cac tap canh <=query va y la tap con lai
thi bao gio x cung duoc unite truoc i va ta can unite den r[i] thi moi khong can i => khi ma i van dong gop la khi 2*query<w[i]+w[r[i]]
tu do tim khoang r can thiet de duy tri mst
*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,m;
    cin>>n>>m;
    for1(i,1,m)cin>>a[i].u>>a[i].v>>a[i].w;
    sort(a+1,a+1+m);
    int q;
    cin>>q;
    for1(i,1,q)cin>>b[i];
    vector<int>use;
    for1(i,1,m){
    for1(j,1,n)f[j]=-1;
    unite(a[i].u,a[i].v);
    vector<int>nw;
    nw.pb(i);
    for (auto u:use){
    if (unite(a[u].u,a[u].v)){
    nw.pb(u);
    }
    else {
    l1[i]=u;
    r1[u]=i;
    }
    }
    use.swap(nw);
    }
    long long cnt1=0,cnt2=0;
    long long w1=0,w2=0;
    for1(i,1,m){
    if (l1[i]==0){
    cnt2++;
    w2+=a[i].w;
    int l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (b[mid]>=a[i].w){
    ans=mid;
    r=mid-1;
    }
    else l=mid+1;
    }
    if (ans!=-1){
    del[ans][1].pb(i);
    add[ans][0].pb(i);
    }
    }
    if (r1[i]==0){
    }
    else {
    int l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (2*b[mid]>=a[i].w+a[r1[i]].w){
    ans=mid;
    r=mid-1;;
    }
    else l=mid+1;
    }
    if (ans!=-1){
    del[ans][0].pb(i);
    add[ans][1].pb(r1[i]);
    l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (b[mid]>=a[r1[i]].w){
    ans=mid;
    r=mid-1;
    }
    else l=mid+1;
    }
    if (ans!=-1){
    del[ans][1].pb(r1[i]);
    add[ans][0].pb(r1[i]);
    }
    }
    else {
    l=1,r=q,ans=-1;
    while (l<=r){
    int mid=(l+r)/2;
    if (b[mid]>=a[r1[i]].w){
    ans=mid;
    r=mid-1;
    }
    else l=mid+1;
    }
    if (ans!=-1){
    del[ans][0].pb(i);
    add[ans][0].pb(r1[i]);
    }
    }
    }
    }
    for1(i,1,q){
    for (auto v:add[i][0]){
    cnt1++;
    w1+=a[v].w;
    }
    for (auto v:add[i][1]){
    cnt2++;
    w2+=a[v].w;
    }
    for (auto v:del[i][0]){
    cnt1--;
    w1-=a[v].w;
    }
    for (auto v:del[i][1]){
    cnt2--;
    w2-=a[v].w;
    }
    cout<<b[i]*cnt1-w1+w2-b[i]*cnt2<<'\n';
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 99056 KB Output is correct
2 Correct 22 ms 98904 KB Output is correct
3 Correct 24 ms 99156 KB Output is correct
4 Correct 22 ms 98904 KB Output is correct
5 Correct 22 ms 98904 KB Output is correct
6 Correct 21 ms 98904 KB Output is correct
7 Correct 22 ms 98904 KB Output is correct
8 Correct 21 ms 99132 KB Output is correct
9 Correct 22 ms 98908 KB Output is correct
10 Correct 22 ms 98908 KB Output is correct
11 Correct 23 ms 98908 KB Output is correct
12 Correct 24 ms 99040 KB Output is correct
13 Correct 24 ms 99164 KB Output is correct
14 Correct 21 ms 98908 KB Output is correct
15 Correct 22 ms 98904 KB Output is correct
16 Correct 21 ms 98908 KB Output is correct
17 Correct 21 ms 98908 KB Output is correct
18 Correct 22 ms 98908 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 99056 KB Output is correct
2 Correct 22 ms 98904 KB Output is correct
3 Correct 24 ms 99156 KB Output is correct
4 Correct 22 ms 98904 KB Output is correct
5 Correct 22 ms 98904 KB Output is correct
6 Correct 21 ms 98904 KB Output is correct
7 Correct 22 ms 98904 KB Output is correct
8 Correct 21 ms 99132 KB Output is correct
9 Correct 22 ms 98908 KB Output is correct
10 Correct 22 ms 98908 KB Output is correct
11 Correct 23 ms 98908 KB Output is correct
12 Correct 24 ms 99040 KB Output is correct
13 Correct 24 ms 99164 KB Output is correct
14 Correct 21 ms 98908 KB Output is correct
15 Correct 22 ms 98904 KB Output is correct
16 Correct 21 ms 98908 KB Output is correct
17 Correct 21 ms 98908 KB Output is correct
18 Correct 22 ms 98908 KB Output is correct
19 Correct 21 ms 99080 KB Output is correct
20 Correct 475 ms 103028 KB Output is correct
21 Correct 383 ms 102780 KB Output is correct
22 Correct 408 ms 103088 KB Output is correct
23 Correct 434 ms 102864 KB Output is correct
24 Correct 472 ms 102784 KB Output is correct
25 Correct 479 ms 103024 KB Output is correct
26 Correct 473 ms 102992 KB Output is correct
27 Correct 483 ms 102816 KB Output is correct
28 Correct 514 ms 103288 KB Output is correct
29 Correct 483 ms 102984 KB Output is correct
30 Correct 474 ms 102704 KB Output is correct
31 Correct 491 ms 102876 KB Output is correct
32 Correct 472 ms 102680 KB Output is correct
33 Correct 475 ms 101972 KB Output is correct
34 Correct 471 ms 101200 KB Output is correct
35 Correct 481 ms 102080 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 98904 KB Output is correct
2 Correct 21 ms 99076 KB Output is correct
3 Correct 24 ms 98904 KB Output is correct
4 Correct 665 ms 133584 KB Output is correct
5 Correct 677 ms 133456 KB Output is correct
6 Correct 664 ms 133456 KB Output is correct
7 Correct 481 ms 135400 KB Output is correct
8 Correct 417 ms 135396 KB Output is correct
9 Correct 369 ms 135504 KB Output is correct
10 Correct 594 ms 121936 KB Output is correct
11 Correct 371 ms 123992 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 99056 KB Output is correct
2 Correct 22 ms 98904 KB Output is correct
3 Correct 24 ms 99156 KB Output is correct
4 Correct 22 ms 98904 KB Output is correct
5 Correct 22 ms 98904 KB Output is correct
6 Correct 21 ms 98904 KB Output is correct
7 Correct 22 ms 98904 KB Output is correct
8 Correct 21 ms 99132 KB Output is correct
9 Correct 22 ms 98908 KB Output is correct
10 Correct 22 ms 98908 KB Output is correct
11 Correct 23 ms 98908 KB Output is correct
12 Correct 24 ms 99040 KB Output is correct
13 Correct 24 ms 99164 KB Output is correct
14 Correct 21 ms 98908 KB Output is correct
15 Correct 22 ms 98904 KB Output is correct
16 Correct 21 ms 98908 KB Output is correct
17 Correct 21 ms 98908 KB Output is correct
18 Correct 22 ms 98908 KB Output is correct
19 Correct 21 ms 98904 KB Output is correct
20 Correct 163 ms 120660 KB Output is correct
21 Correct 167 ms 120660 KB Output is correct
22 Correct 169 ms 120660 KB Output is correct
23 Correct 166 ms 120656 KB Output is correct
24 Correct 192 ms 120604 KB Output is correct
25 Correct 169 ms 120600 KB Output is correct
26 Correct 178 ms 120604 KB Output is correct
27 Correct 185 ms 120660 KB Output is correct
28 Correct 166 ms 120600 KB Output is correct
29 Correct 161 ms 120660 KB Output is correct
30 Correct 169 ms 120916 KB Output is correct
31 Correct 169 ms 120500 KB Output is correct
32 Correct 173 ms 121236 KB Output is correct
33 Correct 163 ms 120208 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 99056 KB Output is correct
2 Correct 22 ms 98904 KB Output is correct
3 Correct 24 ms 99156 KB Output is correct
4 Correct 22 ms 98904 KB Output is correct
5 Correct 22 ms 98904 KB Output is correct
6 Correct 21 ms 98904 KB Output is correct
7 Correct 22 ms 98904 KB Output is correct
8 Correct 21 ms 99132 KB Output is correct
9 Correct 22 ms 98908 KB Output is correct
10 Correct 22 ms 98908 KB Output is correct
11 Correct 23 ms 98908 KB Output is correct
12 Correct 24 ms 99040 KB Output is correct
13 Correct 24 ms 99164 KB Output is correct
14 Correct 21 ms 98908 KB Output is correct
15 Correct 22 ms 98904 KB Output is correct
16 Correct 21 ms 98908 KB Output is correct
17 Correct 21 ms 98908 KB Output is correct
18 Correct 22 ms 98908 KB Output is correct
19 Correct 21 ms 99080 KB Output is correct
20 Correct 475 ms 103028 KB Output is correct
21 Correct 383 ms 102780 KB Output is correct
22 Correct 408 ms 103088 KB Output is correct
23 Correct 434 ms 102864 KB Output is correct
24 Correct 472 ms 102784 KB Output is correct
25 Correct 479 ms 103024 KB Output is correct
26 Correct 473 ms 102992 KB Output is correct
27 Correct 483 ms 102816 KB Output is correct
28 Correct 514 ms 103288 KB Output is correct
29 Correct 483 ms 102984 KB Output is correct
30 Correct 474 ms 102704 KB Output is correct
31 Correct 491 ms 102876 KB Output is correct
32 Correct 472 ms 102680 KB Output is correct
33 Correct 475 ms 101972 KB Output is correct
34 Correct 471 ms 101200 KB Output is correct
35 Correct 481 ms 102080 KB Output is correct
36 Correct 499 ms 104784 KB Output is correct
37 Correct 406 ms 104924 KB Output is correct
38 Correct 456 ms 104924 KB Output is correct
39 Correct 446 ms 105044 KB Output is correct
40 Correct 468 ms 104924 KB Output is correct
41 Correct 523 ms 104788 KB Output is correct
42 Correct 503 ms 104668 KB Output is correct
43 Correct 498 ms 104784 KB Output is correct
44 Correct 499 ms 103652 KB Output is correct
45 Correct 481 ms 103388 KB Output is correct
46 Correct 504 ms 104668 KB Output is correct
47 Correct 503 ms 104700 KB Output is correct
48 Correct 520 ms 104268 KB Output is correct
49 Correct 496 ms 103640 KB Output is correct
50 Correct 472 ms 101520 KB Output is correct
51 Correct 483 ms 102232 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 99056 KB Output is correct
2 Correct 22 ms 98904 KB Output is correct
3 Correct 24 ms 99156 KB Output is correct
4 Correct 22 ms 98904 KB Output is correct
5 Correct 22 ms 98904 KB Output is correct
6 Correct 21 ms 98904 KB Output is correct
7 Correct 22 ms 98904 KB Output is correct
8 Correct 21 ms 99132 KB Output is correct
9 Correct 22 ms 98908 KB Output is correct
10 Correct 22 ms 98908 KB Output is correct
11 Correct 23 ms 98908 KB Output is correct
12 Correct 24 ms 99040 KB Output is correct
13 Correct 24 ms 99164 KB Output is correct
14 Correct 21 ms 98908 KB Output is correct
15 Correct 22 ms 98904 KB Output is correct
16 Correct 21 ms 98908 KB Output is correct
17 Correct 21 ms 98908 KB Output is correct
18 Correct 22 ms 98908 KB Output is correct
19 Correct 21 ms 99080 KB Output is correct
20 Correct 475 ms 103028 KB Output is correct
21 Correct 383 ms 102780 KB Output is correct
22 Correct 408 ms 103088 KB Output is correct
23 Correct 434 ms 102864 KB Output is correct
24 Correct 472 ms 102784 KB Output is correct
25 Correct 479 ms 103024 KB Output is correct
26 Correct 473 ms 102992 KB Output is correct
27 Correct 483 ms 102816 KB Output is correct
28 Correct 514 ms 103288 KB Output is correct
29 Correct 483 ms 102984 KB Output is correct
30 Correct 474 ms 102704 KB Output is correct
31 Correct 491 ms 102876 KB Output is correct
32 Correct 472 ms 102680 KB Output is correct
33 Correct 475 ms 101972 KB Output is correct
34 Correct 471 ms 101200 KB Output is correct
35 Correct 481 ms 102080 KB Output is correct
36 Correct 21 ms 98904 KB Output is correct
37 Correct 21 ms 99076 KB Output is correct
38 Correct 24 ms 98904 KB Output is correct
39 Correct 665 ms 133584 KB Output is correct
40 Correct 677 ms 133456 KB Output is correct
41 Correct 664 ms 133456 KB Output is correct
42 Correct 481 ms 135400 KB Output is correct
43 Correct 417 ms 135396 KB Output is correct
44 Correct 369 ms 135504 KB Output is correct
45 Correct 594 ms 121936 KB Output is correct
46 Correct 371 ms 123992 KB Output is correct
47 Correct 21 ms 98904 KB Output is correct
48 Correct 163 ms 120660 KB Output is correct
49 Correct 167 ms 120660 KB Output is correct
50 Correct 169 ms 120660 KB Output is correct
51 Correct 166 ms 120656 KB Output is correct
52 Correct 192 ms 120604 KB Output is correct
53 Correct 169 ms 120600 KB Output is correct
54 Correct 178 ms 120604 KB Output is correct
55 Correct 185 ms 120660 KB Output is correct
56 Correct 166 ms 120600 KB Output is correct
57 Correct 161 ms 120660 KB Output is correct
58 Correct 169 ms 120916 KB Output is correct
59 Correct 169 ms 120500 KB Output is correct
60 Correct 173 ms 121236 KB Output is correct
61 Correct 163 ms 120208 KB Output is correct
62 Correct 499 ms 104784 KB Output is correct
63 Correct 406 ms 104924 KB Output is correct
64 Correct 456 ms 104924 KB Output is correct
65 Correct 446 ms 105044 KB Output is correct
66 Correct 468 ms 104924 KB Output is correct
67 Correct 523 ms 104788 KB Output is correct
68 Correct 503 ms 104668 KB Output is correct
69 Correct 498 ms 104784 KB Output is correct
70 Correct 499 ms 103652 KB Output is correct
71 Correct 481 ms 103388 KB Output is correct
72 Correct 504 ms 104668 KB Output is correct
73 Correct 503 ms 104700 KB Output is correct
74 Correct 520 ms 104268 KB Output is correct
75 Correct 496 ms 103640 KB Output is correct
76 Correct 472 ms 101520 KB Output is correct
77 Correct 483 ms 102232 KB Output is correct
78 Correct 704 ms 132436 KB Output is correct
79 Correct 613 ms 134372 KB Output is correct
80 Correct 627 ms 133776 KB Output is correct
81 Correct 661 ms 133456 KB Output is correct
82 Correct 666 ms 132584 KB Output is correct
83 Correct 696 ms 126936 KB Output is correct
84 Correct 695 ms 126804 KB Output is correct
85 Correct 694 ms 126292 KB Output is correct
86 Correct 622 ms 116388 KB Output is correct
87 Correct 641 ms 117728 KB Output is correct
88 Correct 678 ms 125412 KB Output is correct
89 Correct 687 ms 125408 KB Output is correct
90 Correct 659 ms 121124 KB Output is correct
91 Correct 655 ms 120404 KB Output is correct
92 Correct 621 ms 116940 KB Output is correct
93 Correct 646 ms 116204 KB Output is correct