oj.uz

Submission #1036187

# Submission time Handle Problem Language Result Execution time Memory
1036187 2024-07-27T04:43:40 Z soncao Robot (JOI21_ho_t4) C++17
24 / 100
 235 ms 69488 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int,int>
#define lll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int>>

const ll oo=1e18;
const int N=6e5+5;

vector<ii> a[N];
vector<pair<int,ii>> g[N];
ll dist[N],sum[N];
bool vis[N];

void dij(int x){
    for(int i=1;i<=N;i++)dist[i]=1e18;
    priority_queue<ii,vector<ii>,greater<ii>> q;
    dist[x]=0;
    q.push({0,x});
    while(!q.empty()){
        auto p1=q.top();q.pop();
        int W=p1.first,x=p1.second;
        if(vis[x])continue;
        vis[x]=1;
        for(auto p2:a[x]){
            int y=p2.first,w=p2.second;
            if(vis[y]||dist[y]<W+w)continue;
            dist[y]=W+w;
            q.push({W+w,y});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
   // freopen("permute.inp","r",stdin);
   // freopen("permute.out","w",stdout);

    int n,m,x,y,c,p;
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>x>>y>>c>>p;
        g[x].push_back({c,{y,p}});
        g[y].push_back({c,{x,p}});
        a[x].push_back({y,p});
        a[y].push_back({x,p});
    }
    int cur=n;
    for(int i=1;i<=n;++i){
        sort(g[i].begin(),g[i].end());
        for(auto x:g[i])
            sum[x.first]+=x.second.second;
        for(auto x:g[i]){
            if(!vis[x.first]){
                ++cur;
                a[i].push_back({cur,0});
            }
            vis[x.first]=1;
            a[cur].push_back({x.second.first,sum[x.first]-x.second.second});
            a[x.second.first].push_back({cur,0});
        }
        for(auto x:g[i]){
            sum[x.first]=0;
            vis[x.first]=0;
        }
    }

    dij(1);
    if(dist[n]==oo)
        cout<<"-1";
    else
        cout<<dist[n];

    return 0;
}

Compilation message

Main.cpp: In function 'void dij(int)':
Main.cpp:18:33: warning: iteration 600004 invokes undefined behavior [-Waggressive-loop-optimizations]
   18 |     for(int i=1;i<=N;i++)dist[i]=1e18;
      |                          ~~~~~~~^~~~~
Main.cpp:18:18: note: within this loop
   18 |     for(int i=1;i<=N;i++)dist[i]=1e18;
      |                 ~^~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33112 KB Output is correct
2 Correct 13 ms 33116 KB Output is correct
3 Correct 13 ms 33276 KB Output is correct
4 Correct 13 ms 33116 KB Output is correct
5 Correct 13 ms 33372 KB Output is correct
6 Incorrect 16 ms 33116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 46284 KB Output is correct
2 Correct 45 ms 39380 KB Output is correct
3 Correct 113 ms 51852 KB Output is correct
4 Correct 66 ms 41576 KB Output is correct
5 Correct 226 ms 69488 KB Output is correct
6 Correct 209 ms 67160 KB Output is correct
7 Correct 157 ms 61632 KB Output is correct
8 Correct 222 ms 63312 KB Output is correct
9 Correct 235 ms 63052 KB Output is correct
10 Correct 135 ms 53232 KB Output is correct
11 Correct 77 ms 48524 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33112 KB Output is correct
2 Correct 13 ms 33116 KB Output is correct
3 Correct 13 ms 33276 KB Output is correct
4 Correct 13 ms 33116 KB Output is correct
5 Correct 13 ms 33372 KB Output is correct
6 Incorrect 16 ms 33116 KB Output isn't correct
7 Halted 0 ms 0 KB -