답안 #973429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
973429	2024-05-02T01:57:35 Z	hotboy2703	Reconstruction Project (JOI22_reconstruction)	C++14	10 / 100	944 ms	57172 KB

reconstruction

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 500;
const ll MAXM = 1e5;
const ll INF = 1e9+7;
struct edge{
    ll u,v,w;
};
edge all[MAXM+100];
pll query[1'000'100];
long long pf[2][1'000'100];
long long ans[1'000'100];
ll dsu[MAXN+100];
ll f(ll x){
    if (dsu[x] < 0)return x;
    return (dsu[x] = f(dsu[x]));
}
void join(ll x,ll y){
    x = f(x),y = f(y);
    if (x!=y){
        if (dsu[x] > dsu[y])swap(x,y);
        dsu[x] += dsu[y];
        dsu[y] = x;
    }
}
ll n,m,q;
pll range[MAXM+100];
vector <ll> mst;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for (ll i = 1;i <= m;i ++){
        cin>>all[i].u>>all[i].v>>all[i].w;
    }
    cin>>q;
    for (ll i = 1;i <= q;i ++){
        cin>>query[i].fi;
        query[i].se = i;
    }
    sort(query+1,query+1+q);



    sort(all+1,all+1+m,[](edge x, edge y){return x.w < y.w;});
    mst.clear();
    for (ll i = 1;i <= m;i ++){
      	assert(sz(mst) < n);
        range[i].fi = -INF;
        for (ll j = 1;j <= n;j ++)dsu[j] = -1;
        ll ptr = 0;
        for (auto x:mst){
            join(all[x].u,all[x].v);
            if (f(all[i].u)==f(all[i].v)){
                mst.erase(mst.begin()+ptr);
                range[i].fi = (all[x].w + all[i].w) / 2 + 1;
                break;
            }
            ptr++;
        }
        mst.insert(mst.begin(),i);
    }
    mst.clear();
    for (ll i = m;i >= 1;i --){assert(sz(mst) < n);
        range[i].se = INF;
        for (ll j = 1;j <= n;j ++)dsu[j] = -1;
        ll ptr = 0;
        for (auto x:mst){
            join(all[x].u,all[x].v);
            if (f(all[i].u)==f(all[i].v)){
                mst.erase(mst.begin()+ptr);
                range[i].se = (all[x].w + all[i].w) / 2;
                break;
            }
            ptr++;
        }
        mst.insert(mst.begin(),i);
    }
    for (ll i = 1;i <= m;i ++){
        if (all[i].w >= range[i].fi){
            ll l = lower_bound(query+1,query+1+q,MP(range[i].fi,-1))-query;
            ll r = upper_bound(query+1,query+1+q,MP(range[i].se,INF))-query-1;
            ll mid = lower_bound(query+1,query+1+q,MP(all[i].w,-1))-query;
            if (l <= r){
                if (l <= mid - 1){
                    // -1 * x + w
                    pf[1][l] += -1;
                    pf[1][mid] -= (-1);
                    pf[0][l] += all[i].w;
                    pf[0][mid] -= all[i].w;
                }
                if (mid <= r){
                    //+1 * x - w
                    pf[1][mid] += +1;
                    pf[1][r+1] -= (+1);
                    pf[0][mid] += -all[i].w;
                    pf[0][r+1] -= -all[i].w;
                }
            }
        }
    }
    for (ll i = 1;i <= q;i ++){
        pf[1][i] += pf[1][i-1];
        pf[0][i] += pf[0][i-1];
        ans[query[i].se] = pf[1][i] * query[i].fi + pf[0][i];
    }
    for (ll i = 1;i <= q;i ++){
        cout<<ans[i]<<'\n';
    }
    cout<<'\n';
}

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10976 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	2 ms	10712 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	2 ms	10588 KB	Output is correct
9	Correct	2 ms	10700 KB	Output is correct
10	Correct	2 ms	10588 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	1 ms	10588 KB	Output is correct
13	Correct	2 ms	10588 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	2 ms	10588 KB	Output is correct
18	Correct	2 ms	10840 KB	Output is correct

Subtask #2
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10976 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	2 ms	10712 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	2 ms	10588 KB	Output is correct
9	Correct	2 ms	10700 KB	Output is correct
10	Correct	2 ms	10588 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	1 ms	10588 KB	Output is correct
13	Correct	2 ms	10588 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	2 ms	10588 KB	Output is correct
18	Correct	2 ms	10840 KB	Output is correct
19	Correct	2 ms	10588 KB	Output is correct
20	Correct	944 ms	12844 KB	Output is correct
21	Correct	367 ms	12884 KB	Output is correct
22	Correct	426 ms	12628 KB	Output is correct
23	Correct	496 ms	12844 KB	Output is correct
24	Correct	664 ms	12840 KB	Output is correct
25	Correct	861 ms	12840 KB	Output is correct
26	Correct	918 ms	12844 KB	Output is correct
27	Correct	923 ms	12840 KB	Output is correct
28	Incorrect	903 ms	12844 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	1 ms	10588 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	653 ms	55264 KB	Output is correct
5	Correct	629 ms	55180 KB	Output is correct
6	Correct	645 ms	55180 KB	Output is correct
7	Correct	283 ms	57028 KB	Output is correct
8	Correct	229 ms	57100 KB	Output is correct
9	Correct	213 ms	57172 KB	Output is correct
10	Correct	598 ms	55180 KB	Output is correct
11	Correct	228 ms	57060 KB	Output is correct

Subtask #4
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10976 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	2 ms	10712 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	2 ms	10588 KB	Output is correct
9	Correct	2 ms	10700 KB	Output is correct
10	Correct	2 ms	10588 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	1 ms	10588 KB	Output is correct
13	Correct	2 ms	10588 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	2 ms	10588 KB	Output is correct
18	Correct	2 ms	10840 KB	Output is correct
19	Correct	2 ms	10840 KB	Output is correct
20	Correct	176 ms	54592 KB	Output is correct
21	Correct	182 ms	54524 KB	Output is correct
22	Correct	157 ms	54460 KB	Output is correct
23	Correct	156 ms	54356 KB	Output is correct
24	Correct	162 ms	54420 KB	Output is correct
25	Correct	177 ms	54608 KB	Output is correct
26	Correct	160 ms	53076 KB	Output is correct
27	Incorrect	162 ms	53200 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10976 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	2 ms	10712 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	2 ms	10588 KB	Output is correct
9	Correct	2 ms	10700 KB	Output is correct
10	Correct	2 ms	10588 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	1 ms	10588 KB	Output is correct
13	Correct	2 ms	10588 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	2 ms	10588 KB	Output is correct
18	Correct	2 ms	10840 KB	Output is correct
19	Correct	2 ms	10588 KB	Output is correct
20	Correct	944 ms	12844 KB	Output is correct
21	Correct	367 ms	12884 KB	Output is correct
22	Correct	426 ms	12628 KB	Output is correct
23	Correct	496 ms	12844 KB	Output is correct
24	Correct	664 ms	12840 KB	Output is correct
25	Correct	861 ms	12840 KB	Output is correct
26	Correct	918 ms	12844 KB	Output is correct
27	Correct	923 ms	12840 KB	Output is correct
28	Incorrect	903 ms	12844 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	1 ms	10588 KB	Output is correct
4	Correct	2 ms	10976 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	2 ms	10712 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	2 ms	10588 KB	Output is correct
9	Correct	2 ms	10700 KB	Output is correct
10	Correct	2 ms	10588 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	1 ms	10588 KB	Output is correct
13	Correct	2 ms	10588 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	2 ms	10588 KB	Output is correct
18	Correct	2 ms	10840 KB	Output is correct
19	Correct	2 ms	10588 KB	Output is correct
20	Correct	944 ms	12844 KB	Output is correct
21	Correct	367 ms	12884 KB	Output is correct
22	Correct	426 ms	12628 KB	Output is correct
23	Correct	496 ms	12844 KB	Output is correct
24	Correct	664 ms	12840 KB	Output is correct
25	Correct	861 ms	12840 KB	Output is correct
26	Correct	918 ms	12844 KB	Output is correct
27	Correct	923 ms	12840 KB	Output is correct
28	Incorrect	903 ms	12844 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #973429

Compilation message

Subtask #1 3.0 / 3.0

Subtask #2 0 / 4.0

Subtask #3 7.0 / 7.0

Subtask #4 0 / 28.0

Subtask #5 0 / 35.0

Subtask #6 0 / 23.0

Subtask #1
3.0 / 3.0

Subtask #2
0 / 4.0

Subtask #3
7.0 / 7.0

Subtask #4
0 / 28.0

Subtask #5
0 / 35.0

Subtask #6
0 / 23.0