oj.uz

Submission #941917

# Submission time Handle Problem Language Result Execution time Memory
941917 2024-03-09T16:54:59 Z Maite_Morale Robot (JOI21_ho_t4) C++14
0 / 100
 476 ms 89336 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll m,n,ans=oo;
vll pass[MAX];
map<ll,ll> node[MAX];
vector<pair<ll,pll>> v[MAX]; 
void distra(ll x,ll y){
    priority_queue<pair<ll,pll>> q;
    q.push({0,{x,0}});
    while(!q.empty()){
        pair<ll,pll> u=q.top();q.pop();
      //  cerr<<u.S.F<<" "<<u.S.S<<": "<<-u.F<<"\n";
        if(pass[u.S.F][node[u.S.F][u.S.S]]!=0)continue;
        pass[u.S.F][node[u.S.F][u.S.S]]=1;
        if(u.S.F==y){
            if(ans==oo)ans=-u.F;
            else       ans=min(ans,-u.F);
        }
        //    if(u.S==y)return -u.F;
        map<ll,ll> mp;
        for(auto w : v[u.S.F]){
            if(w.F==u.S.S || w.F==0)continue;
            mp[w.S.F]+=w.S.S;
        }//cerr<<".";
        for(auto w : v[u.S.F]){
            if(w.F==u.S.S || w.F==0)continue;
           // cerr<<"    "<<w.F<<" "<<min(w.S.S,mp[w.S.F]-w.S.S)<<"\n";
            q.push({u.F-min(w.S.S,mp[w.S.F]-w.S.S),{w.F,u.S.F}});
        }
    }

}
int main(){
    fast_in
    cin>>n>>m;ll a1=1,a2=0,a3=0,a4=0;
    node[a1][a2]=v[a1].size();
    v[a1].push_back({a2,{a3,a4}});
    for(int i=0;i<m;i++){
        cin>>a1>>a2>>a3>>a4;
        node[a1][a2]=v[a1].size();
        node[a2][a1]=v[a2].size();
        v[a1].push_back({a2,{a3,a4}});
        v[a2].push_back({a1,{a3,a4}});
    }
    for(int i=1;i<=n;i++){
        pass[i].assign(v[i].size(),0);
    }
    distra(1,n);
    if(ans==oo)cout<<-1;
    else      cout<<ans;
return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47192 KB Output is correct
2 Correct 11 ms 47196 KB Output is correct
3 Correct 12 ms 47196 KB Output is correct
4 Correct 10 ms 47424 KB Output is correct
5 Correct 12 ms 47456 KB Output is correct
6 Correct 11 ms 47460 KB Output is correct
7 Correct 19 ms 47960 KB Output is correct
8 Correct 14 ms 47792 KB Output is correct
9 Incorrect 476 ms 74248 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 465 ms 89336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47192 KB Output is correct
2 Correct 11 ms 47196 KB Output is correct
3 Correct 12 ms 47196 KB Output is correct
4 Correct 10 ms 47424 KB Output is correct
5 Correct 12 ms 47456 KB Output is correct
6 Correct 11 ms 47460 KB Output is correct
7 Correct 19 ms 47960 KB Output is correct
8 Correct 14 ms 47792 KB Output is correct
9 Incorrect 476 ms 74248 KB Output isn't correct
10 Halted 0 ms 0 KB -