제출 #1101261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101261		thangdz2k7	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	160 ms	25908 KiB

Main

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using li = pair <ll, int>;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, m, s, t, l;
ll k, d[2][N];
vector <ii> adj[N];

priority_queue <li> qu;
const ll inf = 1e18;

void dij(ll *d){
    for (int i = 1; i <= n; ++ i) d[i] ^= inf;
    while (qu.size()){
        auto [du, u] = qu.top(); qu.pop(); du = -du;
        if (du != d[u]) continue;
        for (auto [w, v] : adj[u]){
            if (d[v] > d[u] + w){
                d[v] = d[u] + w;
                qu.push({-d[v], v});
            }
        }
    }
}

void solve(){
    cin >> n >> m;
    cin >> s >> t >> l >> k;
    for (int i = 1, a, b, c; i <= m; ++ i){
        cin >> a >> b >> c;
        adj[a].emplace_back(c, b);
        adj[b].emplace_back(c, a);
    }

    d[0][s] = inf;
    qu.push({0, s});
    dij(d[0]);

    d[1][t] = inf;
    qu.push({0, t});
    dij(d[1]);

    if (d[0][t] <= k){
        cout << ll(n - 1) * n / 2;
        return;
    }

    for (int op : {0, 1}) sort(d[op] + 1, d[op] + n + 1);
    int v = 0; ll ans = 0;
    for (int u = n; u >= 1; -- u){
        while (v < n && d[0][u] + d[1][v + 1] <= k - l) ++ v;
        ans += v;
    }

    cout << ans;
}

int main(){
    if (fopen("solve.inp", "r")){
        freopen("solve.inp", "r", stdin);
        freopen("solve.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
Main.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
Main.cpp:20:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
Main.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
Main.cpp: In function 'int main()':
Main.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen("solve.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("solve.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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