oj.uz

Submission #1119612

# Submission time Handle Problem Language Result Execution time Memory
1119612 2024-11-27T08:09:10 Z InvMOD Construction Project 2 (JOI24_ho_t2) C++14
0 / 100
 7 ms 5452 KB 
#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);

    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--;

        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;
}

Compilation message

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5220 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 4 ms 4956 KB Output is correct
5 Correct 6 ms 5452 KB Output is correct
6 Incorrect 7 ms 5296 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 6 ms 5136 KB Output is correct
3 Correct 6 ms 4952 KB Output is correct
4 Correct 4 ms 5160 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 4 ms 4956 KB Output is correct
9 Correct 4 ms 4956 KB Output is correct
10 Correct 4 ms 5088 KB Output is correct
11 Correct 4 ms 5180 KB Output is correct
12 Incorrect 3 ms 4944 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4948 KB Output is correct
2 Correct 6 ms 5136 KB Output is correct
3 Correct 6 ms 4952 KB Output is correct
4 Correct 4 ms 5160 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 4 ms 4956 KB Output is correct
9 Correct 4 ms 4956 KB Output is correct
10 Correct 4 ms 5088 KB Output is correct
11 Correct 4 ms 5180 KB Output is correct
12 Incorrect 3 ms 4944 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5220 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 4 ms 4956 KB Output is correct
5 Correct 6 ms 5452 KB Output is correct
6 Incorrect 7 ms 5296 KB Output isn't correct
7 Halted 0 ms 0 KB -