oj.uz

Submission #388199

# Submission time Handle Problem Language Result Execution time Memory
388199 2021-04-10T13:33:09 Z BartolM Robot (JOI21_ho_t4) C++17
24 / 100
 2418 ms 127304 KB 
#define DEBUG 1
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;

const int INF=0x3f3f3f3f;
const int N=8e5+5;
const ll MAX=(ll)INF*INF;

int n, m, uk;
map <pii, int> boja, koji, zbr;
ll dist[N];
vector <pil> ls[N];
set <pli> S;

void dijkstra() {
    fill(dist, dist+N, MAX);
    dist[1]=0;
    S.insert(mp(0, 1));
    while (!S.empty()) {
        pli node=*S.begin();
        S.erase(S.begin());
        for (pil sus:ls[node.Y]) {
            if (dist[sus.X]<=sus.Y+node.X) continue;
            if (S.count(mp(dist[sus.X], sus.X))) S.erase(mp(dist[sus.X], sus.X));
            dist[sus.X]=node.X+sus.Y;
            S.insert(mp(dist[sus.X], sus.X));
        }
    }
}

void solve() {
    uk=n+1;
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<ls[i].size(); ++j) {
            pil sus=ls[i][j];
            if (sus.X>n) continue;

            int boj=boja[{i, sus.X}];
            if (!koji[{i, boj}]) {
                ls[i].pb(mp(uk, 0));
                koji[{i, boj}]=uk++;
            }
            int node=koji[{i, boj}];

            ls[sus.X].pb(mp(node, 0));
            ls[node].pb(mp(sus.X, zbr[{i, boj}]-sus.Y));
            assert( zbr[mp(i, boj)]>=sus.Y );
        }
    }
    dijkstra();
    printf("%lld\n", dist[n]>=MAX ? -1 : dist[n]);
}

void load() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; ++i) {
        int a, b, boj, cos;
        scanf("%d %d %d %d", &a, &b, &boj, &cos);
        ls[a].pb(mp(b, cos)); ls[b].pb(mp(a, cos));
        boja[{a, b}]=boj;
        boja[{b, a}]=boj;
        zbr[{a, boj}]+=cos;
        zbr[{b, boj}]+=cos;
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int j=0; j<ls[i].size(); ++j) {
      |                       ~^~~~~~~~~~~~~
Main.cpp: In function 'void load()':
Main.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         scanf("%d %d %d %d", &a, &b, &boj, &cos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25292 KB Output is correct
2 Correct 16 ms 25352 KB Output is correct
3 Correct 16 ms 25256 KB Output is correct
4 Correct 16 ms 25352 KB Output is correct
5 Runtime error 31 ms 38604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 58868 KB Output is correct
2 Correct 201 ms 41552 KB Output is correct
3 Correct 787 ms 68240 KB Output is correct
4 Correct 339 ms 47336 KB Output is correct
5 Correct 2418 ms 127304 KB Output is correct
6 Correct 1962 ms 115264 KB Output is correct
7 Correct 1364 ms 106588 KB Output is correct
8 Correct 1522 ms 95612 KB Output is correct
9 Correct 1571 ms 95500 KB Output is correct
10 Correct 978 ms 80184 KB Output is correct
11 Correct 577 ms 63304 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 25292 KB Output is correct
2 Correct 16 ms 25352 KB Output is correct
3 Correct 16 ms 25256 KB Output is correct
4 Correct 16 ms 25352 KB Output is correct
5 Runtime error 31 ms 38604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -