oj.uz

Submission #973248

# Submission time Handle Problem Language Result Execution time Memory
973248 2024-05-01T16:48:21 Z hotboy2703 Reconstruction Project (JOI22_reconstruction) C++14
3 / 100
 5000 ms 32860 KB 
#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[MAXN+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 ++){
        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 --){
        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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6624 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6624 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Execution timed out 5011 ms 20056 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Execution timed out 5067 ms 32860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6624 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Runtime error 96 ms 17888 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6624 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Execution timed out 5011 ms 20056 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6624 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Execution timed out 5011 ms 20056 KB Time limit exceeded
21 Halted 0 ms 0 KB -