Submission #710465

#	Time	Username	Problem	Language	Result	Execution time	Memory
710465		Ronin13	Robot (JOI21_ho_t4)	C++14	100 / 100	1482 ms	151020 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1000001;
vector <vector <pll> > g(nmax);
ll d[nmax];
vector <bool> used(nmax);
map <pii, int> mp;
int cnt = 0;
vector <vector <pair<pii, int> > >G(200001);
int m;
void process(vector <pii> cur, int v){
    ll s = 0;
    vector <int> vv;
    for(auto to : cur){
        mp[{v, to.s}] = cnt;
        vv.pb(cnt++);
        vv.pb(cnt++);

        s += (ll)to.f;
    }
    for(int j = 0; j < cur.size(); j++){
        int x = vv[j * 2], y = vv[j * 2 + 1];
        g[4 * m + v].pb({y, cur[j].f});
        g[4 * m + v].pb({x, s - (ll)cur[j].f});
        g[x].pb({4 * m + cur[j].s, 0});
        g[y].pb({4 * m + cur[j].s, 0});
    }
}

void process1(vector <pii> cur, int v){
    ll s = 0;
    for(int i = 0; i < cur.size(); i++){
        s += (ll)cur[i].f;
    }
    for(int i = 0; i < cur.size(); i++){
        int x = mp[{cur[i].s, v}];
        x++;
        if(i == cur.size() - 1){
            if(cur.size() == 1) continue;
            int o = cur[cur.size() - 2].s;
            int y = mp[{v, o}];
            g[x].pb({y, s - (ll)cur[i].f - (ll)cur[i - 1].f});
        }
        else{
            int y = cur.back().s;
            y = mp[{v, y}];
            g[x].pb({y, s - (ll)cur[i].f - cur.back().f});
        }
    }
}

int main(){
    int n; cin >> n;
    cin >> m;
    for(int i = 1; i <= m; i++){
        int u, v, c, p; cin >> u >> v >> c >> p;
        G[u].pb({{c, p}, v});
        G[v].pb({{c, p}, u});
    }
    for(int v = 1; v <= n; v++){
        if(G[v].empty()) continue;
        sort(G[v].begin(), G[v].end());
        vector <pii> cur;
        cur.epb(G[v][0].f.s, G[v][0].s);
        for(int i = 1; i < G[v].size(); i++){
            if(G[v][i].f.f == G[v][i - 1].f.f){
                cur.epb(G[v][i].f.s, G[v][i].s);
            }
            else{
                process(cur, v);
                cur.clear();
                cur.epb(G[v][i].f.s, G[v][i].s);
            }
        }
        process(cur, v);
    }
    for(int v = 1; v <= n; v++){
        if(G[v].empty()) continue;
        sort(G[v].begin(), G[v].end());
        vector <pii> cur;
        cur.epb(G[v][0].f.s, G[v][0].s);
        for(int i = 1; i < G[v].size(); i++){
            if(G[v][i].f.f == G[v][i - 1].f.f){
                cur.epb(G[v][i].f.s, G[v][i].s);
            }
            else{
                process1(cur, v);
                cur.clear();
                cur.epb(G[v][i].f.s, G[v][i].s);
            }
        }
        process1(cur, v);
    }
    for(int i = 0; i <= 4 * m + n; i++){
        d[i] = 1e18;
    }
    d[4 * m + 1] = 0;
    priority_queue<pll> q;
    q.push({0, 4 * m + 1});
    while(!q.empty()){
        int v = q.top().s;
        q.pop();
        if(used[v]) continue;
        used[v] = true;
        for(auto ed : g[v]){
            int to = ed.f;
            ll len = ed.s;
            if(d[to] > d[v] + len){
                d[to] = d[v] + len;
                q.push({-d[to], to});
            }
        }
    }
    if(d[4 * m + n] == 1e18)
        cout << -1;
    else
    cout << d[4 * m + n];
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void process(std::vector<std::pair<int, int> >, int)':
Main.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int j = 0; j < cur.size(); j++){
      |                    ~~^~~~~~~~~~~~
Main.cpp: In function 'void process1(std::vector<std::pair<int, int> >, int)':
Main.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < cur.size(); i++){
      |                    ~~^~~~~~~~~~~~
Main.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0; i < cur.size(); i++){
      |                    ~~^~~~~~~~~~~~
Main.cpp:46:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(i == cur.size() - 1){
      |            ~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 1; i < G[v].size(); i++){
      |                        ~~^~~~~~~~~~~~~
Main.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int i = 1; i < G[v].size(); i++){
      |                        ~~^~~~~~~~~~~~~

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