제출 #1119625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119625		InvMOD	Construction Project 2 (JOI24_ho_t2)	C++14	100 / 100	309 ms	29408 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


int n, m, S, T;

ll dist[2][N], L, K;

vector<pair<int,ll>> adj[N];

void dijkstra(int id, int source){
    priority_queue<pair<ll,int>> pq;

    FOR(i, 1, n){
        if(i == source){
            dist[id][i] = 0;
            pq.push(make_pair(0, i));
        }
        else dist[id][i] = INF;
    }

    while(!pq.empty()){
        pair<ll,int> eq = pq.top(); pq.pop();

        ll cur_dist = -eq.first; int x = eq.second;
        if(cur_dist > dist[id][x]) continue;

        for(pair<int,ll> e : adj[x]){
            int v = e.first; ll w = e.second;
            if(dist[id][v] > cur_dist + w){
                dist[id][v] = cur_dist + w;
                pq.push(make_pair(-dist[id][v], v));
            }
        }
    }
    return;
}

void solve()
{
    cin >> n >> m >> S >> T >> L >> K;
    FOR(i, 1, m){
        int u,v; ll w; cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }

    dijkstra(0, S);
    dijkstra(1, T);

    if(dist[0][T] <= K){
        cout << (1ll * n * (n - 1)) / 2ll <<"\n";
        return;
    }

    vector<int> idS(n+1); iota(1 + all(idS), 1);
    vector<int> idT(n+1); iota(1 + all(idT), 1);

    sort(1 + all(idS), [&](int u, int v){
        return dist[0][u] < dist[0][v];
    });

    sort(1 + all(idT), [&](int u, int v){
        return dist[1][u] < dist[1][v];
    });

    vector<bool> rem(n+1, true);

    ll answer = 0;
    for(int i = 1, j = n; i <= n; i++){
        int u = idS[i];
        while(j > 0 && dist[1][idT[j]] + dist[0][u] + L > K) rem[idT[j]] = false, j--;
        if(dist[0][u] + dist[1][u] <= K){
            answer = answer + (n - u);
        }
        else answer = answer + 1ll * ((j > 0 ? j - rem[u] : j));
    }

    cout << answer <<"\n";
    return;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

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

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

Main.cpp: In function 'int main()':
Main.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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