oj.uz

답안 #973234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973234 2024-05-01T16:39:03 Z hotboy2703 Reconstruction Project (JOI22_reconstruction) C++17
3 / 100
 5000 ms 53332 KB 
#include<bits/stdc++.h>
using ll = long long;
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 = 1e18;
struct edge{
    ll u,v,w;
};
edge all[MAXM+100];
pll query[1'000'100];
ll pf[2][1'000'100];
ll 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[MAXN+100];
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);

    vector <ll> mst;

    sort(all+1,all+1+m,[](edge x, edge y){return x.w < y.w;});
    mst.clear();
    for (ll i = 1;i <= m;i ++){
//        cout<<i<<' '<<sz(mst)<<endl;
        range[i].fi = -INF;
        for (ll j = 1;j <= n;j ++)dsu[j] = -1;
        for (auto x:mst){
            join(all[x].u,all[x].v);
            if (f(all[i].u)==f(all[i].v)){
                range[i].fi = (all[x].w + all[i].w) / 2 + 1;
                break;
            }
        }

        mst.insert(mst.begin(),i);
        for (ll j = 1;j <= n;j ++)dsu[j] = -1;
        for (ll j = 0;j < sz(mst);j ++){
            if (f(all[mst[j]].u) == f(all[mst[j]].v)){
                mst.erase(mst.begin()+j);
                j--;
            }
            else {
                join(all[mst[j]].u,all[mst[j]].v);
            }
        }
    }
    mst.clear();
    for (ll i = m;i >= 1;i --){
        range[i].se = INF;
        for (ll j = 1;j <= n;j ++)dsu[j] = -1;
        for (auto x:mst){
            join(all[x].u,all[x].v);
            if (f(all[i].u)==f(all[i].v)){
                range[i].se = (all[x].w + all[i].w) / 2;
                break;
            }
        }
        mst.insert(mst.begin(),i);
        for (ll j = 1;j <= n;j ++)dsu[j] = -1;
        for (ll j = 0;j < sz(mst);j ++){
            if (f(all[mst[j]].u) == f(all[mst[j]].v)){
                mst.erase(mst.begin()+j);
                j--;
            }
            else {
                join(all[mst[j]].u,all[mst[j]].v);
            }
        }
    }
//    for (ll i = 1;i <= m;i ++){
//        cout<<all[i].u<<' '<<all[i].v<<' '<<all[i].w<<'\n';
//    }
//    for (ll i = 1;i <= m;i ++){
//        cout<<range[i].fi<<' '<<range[i].se<<'\n';
//    }
//    for (ll i = 1;i <= q;i ++){
//        cout<<query[i].fi<<'\n';
//    }
    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,-1LL))-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,-1LL))-query;
            if (l <= r){
//                cout<<l<<' '<<r<<' '<<mid<<'\n';
                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];
//        cout<<pf[1][i]<<' '<<pf[0][i]<<'\n';
        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 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8652 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8652 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Execution timed out 5071 ms 37424 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8648 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Execution timed out 5058 ms 53332 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8652 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8536 KB Output is correct
20 Runtime error 120 ms 47556 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8652 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Execution timed out 5071 ms 37424 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8652 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Execution timed out 5071 ms 37424 KB Time limit exceeded
21 Halted 0 ms 0 KB -