Submission #1137868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137868		marchell_hii	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	148 ms	24420 KiB

Main

/*
 ███╗   ███╗ █████╗ ██████╗ ███████╗    ██████╗ ██╗   ██╗       ███╗   ███╗ █████╗ ██████╗  ██████╗██╗  ██╗███████╗██╗     ██╗           ██╗  ██╗██╗██╗
 ████╗ ████║██╔══██╗██╔══██╗██╔════╝    ██╔══██╗╚██╗ ██╔╝██╗    ████╗ ████║██╔══██╗██╔══██╗██╔════╝██║  ██║██╔════╝██║     ██║           ██║  ██║██║██║
 ██╔████╔██║███████║██║  ██║█████╗      ██████╔╝ ╚████╔╝ ╚═╝    ██╔████╔██║███████║██████╔╝██║     ███████║█████╗  ██║     ██║           ███████║██║██║
 ██║╚██╔╝██║██╔══██║██║  ██║██╔══╝      ██╔══██╗  ╚██╔╝  ██╗    ██║╚██╔╝██║██╔══██║██╔══██╗██║     ██╔══██║██╔══╝  ██║     ██║           ██╔══██║██║██║
 ██║ ╚═╝ ██║██║  ██║██████╔╝███████╗    ██████╔╝   ██║   ╚═╝    ██║ ╚═╝ ██║██║  ██║██║  ██║╚██████╗██║  ██║███████╗███████╗███████╗█████╗██║  ██║██║██║
 ╚═╝     ╚═╝╚═╝  ╚═╝╚═════╝ ╚══════╝    ╚═════╝    ╚═╝          ╚═╝     ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝ ╚═════╝╚═╝  ╚═╝╚══════╝╚══════╝╚══════╝╚════╝╚═╝  ╚═╝╚═╝╚═╝
*/
/*
 ඞ
 ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣤⣤⣤⣤⣤⣤⣤⣤⣄⡀
 ⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⡿⠛⠉⠉⠉⠉⠉⠉⠻⢿⣿⣷⡄
 ⠀⠀⠀⠀⠀⠀⠀⠀⣼⣿⠋⠀⠀⠀⠀⠀⠀⠀      ⢻⣿⣿⡄
 ⠀⠀⠀⠀⠀⠀⠀⣸⣿⡏⠀⠀⠀   ⣠⣾⣿⣿⣿⠿⠿⠿⢿⣿⣿⣄
 ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠁⠀⠀    ⣿⣿⣯⠁⠀⠀⠀⠀⠀  ⠙⢿⣷⡄
 ⠀⠀⣀⣤⣴⣶⣶⣿⡟⠀⠀⠀   ⣿⣿⣿            ⣿⣷
 ⠀⢰⣿⡟⠋⠉⣹⣿⡇⠀⠀⠀   ⣿⣿⣿⣷⣦⣀⣀⣀⣀⣀⣀⣀⣿⣿
  ⢸⣿⡇   ⣿⣿⡇⠀⠀     ⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  ⣸⣿⡇   ⣿⣿⡇⠀⠀⠀⠀    ⠉⠉⠉⠉⠉⠉⠉⠉⠉⡿⢻⡇
 ⠀⣿⣿    ⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀       ⢸⣿⡇
 ⠀⣿⣿⠀   ⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀      ⢸⣿⡇
 ⠀⣿⣿⠀⠀  ⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀      ⢸⣿⡇
 ⠀⢿⣿   ⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀         ⣿⡇
 ⠀⠸⣿⣦⡀⠀⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀       ⣿⣿
 ⠀⠀⠛⢿⣿⣿⣿⣿⡇    ⠀⣠⣿⣿⣿⣿⣄       ⣿⣿
 ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠀⠀⠀⠀⠀⣿⣿⡇⠀⣽⣿⡆     ⢸⣿⡇
 ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠀⠀⠀⠀⠀⣿⣿⡇⠀⢹⣿⡆⠀⠀   ⣸⣿⠇
 ⠀⠀⠀⠀⠀⠀⠀⢿⣿⣦⣄⣀⣠⣴⣿⣿ ⠀⠈⠻⣿⣿⣿⣿⡿⠏
 ⠀⠀⠀⠀⠀⠀⠀⠈⠛⠻⠿⠿⠿⠿⠋⠁
*/
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, pll>
#define pdd pair<double, double>
#define pu push_back
#define po pop_back
#define fi first
#define se second
#define fifi fi.fi
#define fise fi.se
#define sefi se.fi
#define sese se.se
#define cekcek cout<<'c'<<'e'<<'k'<<endl
using namespace std;

ll N, M, S, T, l, K, a, b, c, dist[200005][2], L, R, mid, pos, ans;
vector<pll> adj[200005];
priority_queue<pll, vector<pll>, greater<pll>> q;
pll now;
vector<ll> v;



void F(ll x, ll y){
    for(ll i = 1; i <= N; i++) dist[i][y] = 1e16;
    dist[x][y] = 0;
    q.push({0, x});
    while(!q.empty()){
        now = q.top();
        q.pop();
        if(now.fi > dist[now.se][y]) continue;
        for(auto i : adj[now.se]){
            if(now.fi + i.se < dist[i.fi][y]){
                dist[i.fi][y] = now.fi + i.se;
                q.push({dist[i.fi][y], i.fi});
            }
        }
    }
    return;
}

bool compare(ll x, ll y){
    return dist[x][1] > dist[y][1];
}

int main(){
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
cin >> S >> T >> l >> K;
for(ll j = 1; j <= M; j++){
    cin >> a >> b >> c;
    adj[a].pu({b, c});
    adj[b].pu({a, c});
}
F(S, 0);
F(T, 1);
if(dist[T][0] <= K){
    cout << N * (N - 1) / 2 << endl;
    return 0;
}
for(ll i = 1; i <= N; i++) v.pu(i);
sort(v.begin(), v.end(), compare);
for(ll i = 0; i < N - 1; i++){
    if(dist[v[i]][0] > K) continue;
    L = i + 1;
    R = N - 1;
    pos = 0;
    while(L <= R){
        mid = (L + R) / 2;
        if(dist[v[i]][0] + l + dist[v[mid]][1] <= K){
            R = mid - 1;
            pos = N - mid;
        }
        else L = mid + 1;
    }
    ans += pos;
}
cout << ans << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 47 / 47