oj.uz

Submission #1095699

# Submission time Handle Problem Language Result Execution time Memory
1095699 2024-10-03T02:32:02 Z DucNguyen2007 Construction Project 2 (JOI24_ho_t2) C++14
0 / 100
 5 ms 10076 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,m,s,t,l;
ll k;
struct duongdi
{
    int u;
    ll w;
    bool operator < (const duongdi &o)const
    {
        return w>o.w;
    }
};
ll d[2][maxN+1];
vector<duongdi> adj[maxN+1];
priority_queue<duongdi> pq;
vector<pll> vec1[maxN+1],vec2;
void dijkstra(int s,int type)
{
    for(int i=1;i<=n;i++)
    {
        d[type][i]=inf;
    }
    d[type][s]=0;
    pq.push({s,0});
    while(!pq.empty())
    {
        duongdi tmp=pq.top();
        pq.pop();
        int u=tmp.u;
        ll w=tmp.w;
        if(d[type][u]<w)
        {
            continue;
        }
        for(auto [v,nw]:adj[u])
        {
            if(d[type][v]>d[type][u]+nw)
            {
                d[type][v]=d[type][u]+nw;
                pq.push({v,d[type][v]});
            }
        }
    }
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s>>t>>l>>k;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dijkstra(s,0);
    dijkstra(t,1);
    sort(d[0]+1,d[0]+n+1);
    sort(d[1]+1,d[1]+n+1);
    ll ans=0;
    for(int i=1,j=n;i<=n;i++)
    {
        while(j>0&&d[0][i]+d[1][j]+l>k)
        {
            j--;
        }
        ans+=j;
    }
    cout<<ans;
}

Compilation message

Main.cpp: In function 'void dijkstra(int, int)':
Main.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for(auto [v,nw]:adj[u])
      |                  ^

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 10072 KB Output is correct
6 Incorrect 5 ms 10076 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 4 ms 9820 KB Output is correct
2 Correct 4 ms 9620 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9872 KB Output is correct
6 Correct 4 ms 9864 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9800 KB Output is correct
9 Correct 4 ms 9816 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 4 ms 9820 KB Output is correct
12 Incorrect 4 ms 10072 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 4 ms 9820 KB Output is correct
2 Correct 4 ms 9620 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9872 KB Output is correct
6 Correct 4 ms 9864 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9800 KB Output is correct
9 Correct 4 ms 9816 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 4 ms 9820 KB Output is correct
12 Incorrect 4 ms 10072 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 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 10072 KB Output is correct
6 Incorrect 5 ms 10076 KB Output isn't correct
7 Halted 0 ms 0 KB -