Submission #640067

#	Time	Username	Problem	Language	Result	Execution time	Memory
640067		victor_gao	Robot (JOI21_ho_t4)	C++17	100 / 100	1048 ms	105640 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m;
struct Edge{
    int to,col,cost;
    Edge(int a,int b,int c):to(a),cost(b),col(c){}
};
map<int,int>dis[N],all[N];
vector<Edge>g[N];
map<int,vector<pii> >ng[N];
signed main(){
    fast
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int a,b,c,d; cin>>a>>b>>c>>d;
        g[a].push_back(Edge(b,d,c));
        g[b].push_back(Edge(a,d,c));
        ng[a][c].push_back({b,d});
        ng[b][c].push_back({a,d});
        all[a][c]+=d;
        all[b][c]+=d;
    }
    dis[1][0]=0;
    priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > >pq;
    pq.push({0,{1,0}});
    while (!pq.empty()){
        auto np=pq.top(); pq.pop();
        if (dis[np.y.x][np.y.y]!=np.x) continue;
        if (np.y.y){
            for (auto i:ng[np.y.x][np.y.y]){
                int new_cost=all[np.y.x][np.y.y]-i.y;
                if (!dis[i.x].count(0)||dis[i.x][0]>np.x+new_cost){
                    dis[i.x][0]=np.x+new_cost;
                    pq.push({np.x+new_cost,{i.x,0}});
                }
            }
        }
        else {
            for (auto i:g[np.y.x]){
                int new_cost=min(all[np.y.x][i.col]-i.cost,i.cost);
                if (!dis[i.to].count(0)||dis[i.to][0]>np.x+new_cost){
                    dis[i.to][0]=np.x+new_cost;
                    pq.push({np.x+new_cost,{i.to,0}});
                }
                new_cost=0;
                if (!dis[i.to].count(i.col)||dis[i.to][i.col]>np.x+new_cost){
                    dis[i.to][i.col]=np.x+new_cost;
                    pq.push({np.x+new_cost,{i.to,i.col}});
                }
            }
        }
    }
    if (!dis[n].count(0)) cout<<-1<<'\n';
    else cout<<dis[n][0]<<'\n';
}

Compilation message (stderr)

Main.cpp: In constructor 'Edge::Edge(long long int, long long int, long long int)':
Main.cpp:19:16: warning: 'Edge::cost' will be initialized after [-Wreorder]
   19 |     int to,col,cost;
      |                ^~~~
Main.cpp:19:12: warning:   'long long int Edge::col' [-Wreorder]
   19 |     int to,col,cost;
      |            ^~~
Main.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     Edge(int a,int b,int c):to(a),cost(b),col(c){}
      |     ^~~~

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42