oj.uz

Submission #668334

# Submission time Handle Problem Language Result Execution time Memory
668334 2022-12-03T16:31:33 Z urosk Robot (JOI21_ho_t4) C++14
100 / 100
 783 ms 85380 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 100005
ll n,m;
map<ll,vector<pll> > g[maxn];
map<ll,ll> scol[maxn];
map<ll,ll> dis[maxn];
ll dis2[maxn];
struct str{
    ll u,d,c;
};
bool cmp(str a,str b){
    return a.d>b.d;
}
priority_queue<str,vector<str>,decltype(&cmp)> pq(cmp);
void tc(){
    cin >> n >> m;
    for(ll i = 1;i<=m;i++){
        ll x,y,c,w; cin >> x >> y >> c >> w;
        g[x][c].pb({y,w});
        g[y][c].pb({x,w});
        scol[x][c]+=w;
        scol[y][c]+=w;
    }
    fill(dis2,dis2+maxn,llinf);
    dis2[1] = 0;
    pq.push({1,0,0});
    while(sz(pq)){
        str cur = pq.top();
        pq.pop();
        ll u = cur.u;
        ll d = cur.d;
        ll c = cur.c;

        if(c){
            if(dis[u][c]!=d) continue;
            for(pll p : g[u][c]){
                ll v = p.fi;
                ll w = p.sc;
                if(dis2[v]>scol[u][c]+d-w){
                    dis2[v] = scol[u][c]+d-w;
                    pq.push({v,dis2[v],0});
                }
            }
        }else{
            if(dis2[u]!=d) continue;
            for(auto r : g[u]){
                ll col = r.fi;
                for(pll p : r.sc){
                    ll v = p.fi;
                    ll w = p.sc;
                    ll dcur = min(scol[u][col]-w,w);
                    if(dis2[v]>d+dcur){
                        dis2[v] = d+dcur;
                        pq.push({v,dis2[v],0});
                    }
                    if(dis[v].find(col)==dis[v].end()||dis[v][col]>d){
                        dis[v][col] = d;
                        pq.push({v,dis[v][col],col});
                    }
                }
            }
        }
    }
    ll ans = dis2[n];
    if(ans==llinf) ans = -1;
    cout<<ans<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 8 ms 15192 KB Output is correct
3 Correct 9 ms 15184 KB Output is correct
4 Correct 7 ms 15196 KB Output is correct
5 Correct 8 ms 15192 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 8 ms 15384 KB Output is correct
8 Correct 8 ms 15228 KB Output is correct
9 Correct 11 ms 15856 KB Output is correct
10 Correct 10 ms 15712 KB Output is correct
11 Correct 9 ms 15572 KB Output is correct
12 Correct 10 ms 15464 KB Output is correct
13 Correct 9 ms 15548 KB Output is correct
14 Correct 9 ms 15588 KB Output is correct
15 Correct 9 ms 15444 KB Output is correct
16 Correct 9 ms 15492 KB Output is correct
17 Correct 9 ms 15584 KB Output is correct
18 Correct 8 ms 15316 KB Output is correct
19 Correct 9 ms 15456 KB Output is correct
20 Correct 9 ms 15444 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 34996 KB Output is correct
2 Correct 79 ms 25352 KB Output is correct
3 Correct 209 ms 32456 KB Output is correct
4 Correct 109 ms 28396 KB Output is correct
5 Correct 775 ms 83328 KB Output is correct
6 Correct 600 ms 72744 KB Output is correct
7 Correct 300 ms 55204 KB Output is correct
8 Correct 374 ms 50888 KB Output is correct
9 Correct 386 ms 50920 KB Output is correct
10 Correct 298 ms 48316 KB Output is correct
11 Correct 121 ms 32712 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 8 ms 15192 KB Output is correct
3 Correct 9 ms 15184 KB Output is correct
4 Correct 7 ms 15196 KB Output is correct
5 Correct 8 ms 15192 KB Output is correct
6 Correct 7 ms 15188 KB Output is correct
7 Correct 8 ms 15384 KB Output is correct
8 Correct 8 ms 15228 KB Output is correct
9 Correct 11 ms 15856 KB Output is correct
10 Correct 10 ms 15712 KB Output is correct
11 Correct 9 ms 15572 KB Output is correct
12 Correct 10 ms 15464 KB Output is correct
13 Correct 9 ms 15548 KB Output is correct
14 Correct 9 ms 15588 KB Output is correct
15 Correct 9 ms 15444 KB Output is correct
16 Correct 9 ms 15492 KB Output is correct
17 Correct 9 ms 15584 KB Output is correct
18 Correct 8 ms 15316 KB Output is correct
19 Correct 9 ms 15456 KB Output is correct
20 Correct 9 ms 15444 KB Output is correct
21 Correct 195 ms 34996 KB Output is correct
22 Correct 79 ms 25352 KB Output is correct
23 Correct 209 ms 32456 KB Output is correct
24 Correct 109 ms 28396 KB Output is correct
25 Correct 775 ms 83328 KB Output is correct
26 Correct 600 ms 72744 KB Output is correct
27 Correct 300 ms 55204 KB Output is correct
28 Correct 374 ms 50888 KB Output is correct
29 Correct 386 ms 50920 KB Output is correct
30 Correct 298 ms 48316 KB Output is correct
31 Correct 121 ms 32712 KB Output is correct
32 Correct 111 ms 29400 KB Output is correct
33 Correct 146 ms 30868 KB Output is correct
34 Correct 392 ms 50968 KB Output is correct
35 Correct 293 ms 42184 KB Output is correct
36 Correct 276 ms 47260 KB Output is correct
37 Correct 351 ms 50420 KB Output is correct
38 Correct 323 ms 61332 KB Output is correct
39 Correct 138 ms 33004 KB Output is correct
40 Correct 423 ms 52228 KB Output is correct
41 Correct 430 ms 52512 KB Output is correct
42 Correct 490 ms 61152 KB Output is correct
43 Correct 206 ms 37652 KB Output is correct
44 Correct 374 ms 43628 KB Output is correct
45 Correct 297 ms 47700 KB Output is correct
46 Correct 265 ms 47816 KB Output is correct
47 Correct 316 ms 49876 KB Output is correct
48 Correct 783 ms 85380 KB Output is correct