oj.uz

Submission #998089

# Submission time Handle Problem Language Result Execution time Memory
998089 2024-06-13T09:37:03 Z Malix Construction Project 2 (JOI24_ho_t2) C++14
45 / 100
 2000 ms 21224 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

vector<vector<pair<int,ll>>> a;

void djikistra(vector<ll> &c,int s){
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    c[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        ll x=pq.top().F;
        int y=pq.top().S;
        pq.pop();
        if(c[y]<x)continue;
        for(auto u:a[y]){
            if(c[u.F]<c[y]+u.S)continue;
            c[u.F]=c[y]+u.S;
            pq.push({c[u.F],u.F});
        }
    }

}

int main() {   
//ios::sync_with_stdio(0);
//cin.tie(0);
//freopen("test_input.txt", "r", stdin);
//freopen("test_output.txt", "w", stdout);
    int n,m;cin>>n>>m;
    int s,t;ll l,k;cin>>s>>t>>l>>k;
    s--;t--;
    a.resize(n);
    vector<ll> b(n,INF),c(n,INF);
    REP(i,0,m){
        int x,y,z;cin>>x>>y>>z;
        x--;y--;
        a[x].PB({y,z});
        a[y].PB({x,z});
    }
    djikistra(b,s);
    djikistra(c,t);
    if(b[t]<=k){
        cout<<((ll)n*(n-1))/2;
        return 0;
    }
    sort(c.begin(),c.end());
    ll ans=0;
    REP(i,0,n)ans+=upper_bound(c.begin(),c.end(),k-l-b[i])-c.begin();
    cout<<ans;
}

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 99 ms 17296 KB Output is correct
8 Correct 113 ms 17256 KB Output is correct
9 Correct 102 ms 17592 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 67 ms 13464 KB Output is correct
15 Correct 193 ms 19324 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 664 KB Output is correct
18 Correct 122 ms 17596 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 66 ms 13404 KB Output is correct
24 Correct 200 ms 19320 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 127 ms 21224 KB Output is correct
28 Execution timed out 2032 ms 13876 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 428 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 428 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 2 ms 604 KB Output is correct
34 Correct 2 ms 592 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 2 ms 604 KB Output is correct
37 Correct 2 ms 604 KB Output is correct
38 Correct 1 ms 604 KB Output is correct
39 Correct 2 ms 604 KB Output is correct
40 Correct 2 ms 604 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 4 ms 604 KB Output is correct
44 Correct 4 ms 724 KB Output is correct
45 Correct 4 ms 856 KB Output is correct
46 Correct 3 ms 604 KB Output is correct
47 Correct 2 ms 600 KB Output is correct
48 Correct 2 ms 604 KB Output is correct
49 Correct 2 ms 604 KB Output is correct
50 Correct 1 ms 604 KB Output is correct
51 Correct 6 ms 704 KB Output is correct
52 Correct 5 ms 600 KB Output is correct
53 Correct 2 ms 604 KB Output is correct
54 Correct 3 ms 604 KB Output is correct
55 Correct 2 ms 604 KB Output is correct
56 Correct 2 ms 648 KB Output is correct
57 Correct 2 ms 604 KB Output is correct
58 Correct 2 ms 640 KB Output is correct

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 99 ms 17296 KB Output is correct
8 Correct 113 ms 17256 KB Output is correct
9 Correct 102 ms 17592 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 67 ms 13464 KB Output is correct
15 Correct 193 ms 19324 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 664 KB Output is correct
18 Correct 122 ms 17596 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 66 ms 13404 KB Output is correct
24 Correct 200 ms 19320 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 127 ms 21224 KB Output is correct
28 Execution timed out 2032 ms 13876 KB Time limit exceeded
29 Halted 0 ms 0 KB -