oj.uz

Submission #639024

# Submission time Handle Problem Language Result Execution time Memory
639024 2022-09-08T09:46:59 Z danikoynov Robot (JOI21_ho_t4) C++14
100 / 100
 1716 ms 162444 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;


struct edge
{
    int ver;
    ll len;

    edge(int _ver = 0, ll _len = 0)
    {
        ver = _ver;
        len = _len;
    }

    bool operator < (const edge &e) const
    {
        return len > e.len;
    }
};


const int maxn = 2e6 + 10;

int n, m, nxt;
map < pair < int, int >, int > mp;
map < pair < int, int >, ll > sum;
vector < edge > g[maxn];

int mp_idx(int v, int c)
{
    if (mp.find(make_pair(v, c)) == mp.end())
        mp[make_pair(v, c)] = ++ nxt;
    return mp[make_pair(v, c)];
}

struct road
{
    int v, u, c, p;

    road(int _v = 0, int _u = 0, int _c = 0, int _p = 0)
    {
        v = _v;
        u = _u;
        c = _c;
        p = _p;
    }
}r[maxn];

const ll inf = 1e18;
ll d[maxn];
int used[maxn];

void add_edge(int v, edge e)
{
    g[v].push_back(e);
    ///cout << v << " " << e.ver << " " << e.len << endl;
}
void solve()
{
    cin >> n >> m;
    nxt = n;
    for (int i = 1; i <= m; i ++)
    {
        int v, u, c, p;
        cin >> v >> u >> c >> p;
        r[i] = road(v, u, c, p);
        for (int t = 0; t < 2; t ++)
        {
            swap(v, u);
            ///g[v].push_back(edge(u, p));
            add_edge(v, edge(u, p));
            add_edge(v, edge(mp_idx(u, c), 0));
            ///g[v].push_back(edge(mp_idx(u, c), 0));

            ///cout << "to_add " << v << " " << c << " " << p << endl;
            sum[make_pair(v, c)] += p;
        }
    }

    map < pair < int, int >, int > :: iterator it;
    for (int i = 1; i <= m; i ++)
    {      int v = r[i].v, u = r[i].u, c = r[i].c, p = r[i].p;
        for (int t = 0; t < 2; t ++)
        {
           swap(v, u);
           add_edge(v, edge(u, sum[make_pair(v, c)] - p));
           add_edge(mp_idx(v, c), edge(u, sum[make_pair(v, c)] - p));
        }
    }
    /**for (it = mp.begin(); it != mp.end(); it ++)
    {
        pair < int, int > cur = it -> first;
        for (int j = 0; j < g[cur.first].size(); j ++)
        {
            int ver = g[cur.first][j].ver;
            if (ver <= n)
            {
                ///g[mp_idx(cur.first, cur.second)].push_back(edge(ver, sum[cur] - g[cur.first][j].len));
                cout << cur.first << " :: " << cur.second << " :: " << sum[cur] << " " << g[cur.first][j].len << endl;
                add_edge(mp_idx(cur.first, cur.second), edge(ver, sum[cur] - g[cur.first][j].len));
            }
        }
    }*/

    for (int i = 1; i <= m; i ++)
    {
        int v = r[i].v, u = r[i].u, c = r[i].c, p = r[i].p;
        for (int t = 0; t < 2; t ++)
        {
            swap(v, u);
            if (sum[make_pair(v, c)] == p)
            {
                ///g[v].push_back(edge(u, 0));
                add_edge(v, edge(u, 0));

            }
        }
    }

    for (int i = 1; i <= nxt; i ++)
        d[i] = inf;
    priority_queue < edge > pq;
    pq.push(edge(1, 0));
    d[1] = 0;
    while(!pq.empty())
    {
        edge e = pq.top();
        pq.pop();
        if (d[e.ver] >= e.len)
            if (!used[e.ver])
        {
            used[e.ver] = 1;
            for (int j = 0; j < g[e.ver].size(); j ++)
            {
                edge nb =  g[e.ver][j];
                nb.len += e.len;
                if (nb.len < d[nb.ver])
                {
                    d[nb.ver] = nb.len;
                    pq.push(nb);
                }
            }
        }
    }

    if (d[n] == inf)
        cout << -1 << endl;
    else
        cout << d[n] << endl;

}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    ///freopen("input.txt", "r", stdin);
    speed();
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:137:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             for (int j = 0; j < g[e.ver].size(); j ++)
      |                             ~~^~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78540 KB Output is correct
2 Correct 34 ms 78616 KB Output is correct
3 Correct 35 ms 78548 KB Output is correct
4 Correct 36 ms 78496 KB Output is correct
5 Correct 37 ms 78540 KB Output is correct
6 Correct 38 ms 78668 KB Output is correct
7 Correct 39 ms 78804 KB Output is correct
8 Correct 36 ms 78708 KB Output is correct
9 Correct 47 ms 79384 KB Output is correct
10 Correct 42 ms 79328 KB Output is correct
11 Correct 39 ms 79196 KB Output is correct
12 Correct 39 ms 78968 KB Output is correct
13 Correct 38 ms 79204 KB Output is correct
14 Correct 39 ms 79180 KB Output is correct
15 Correct 39 ms 78864 KB Output is correct
16 Correct 41 ms 79096 KB Output is correct
17 Correct 45 ms 79104 KB Output is correct
18 Correct 37 ms 78752 KB Output is correct
19 Correct 38 ms 78976 KB Output is correct
20 Correct 39 ms 79024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 104432 KB Output is correct
2 Correct 207 ms 91144 KB Output is correct
3 Correct 550 ms 110476 KB Output is correct
4 Correct 284 ms 95724 KB Output is correct
5 Correct 1667 ms 156952 KB Output is correct
6 Correct 1423 ms 150588 KB Output is correct
7 Correct 790 ms 138516 KB Output is correct
8 Correct 1317 ms 138076 KB Output is correct
9 Correct 1298 ms 138220 KB Output is correct
10 Correct 901 ms 124360 KB Output is correct
11 Correct 561 ms 111464 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 78540 KB Output is correct
2 Correct 34 ms 78616 KB Output is correct
3 Correct 35 ms 78548 KB Output is correct
4 Correct 36 ms 78496 KB Output is correct
5 Correct 37 ms 78540 KB Output is correct
6 Correct 38 ms 78668 KB Output is correct
7 Correct 39 ms 78804 KB Output is correct
8 Correct 36 ms 78708 KB Output is correct
9 Correct 47 ms 79384 KB Output is correct
10 Correct 42 ms 79328 KB Output is correct
11 Correct 39 ms 79196 KB Output is correct
12 Correct 39 ms 78968 KB Output is correct
13 Correct 38 ms 79204 KB Output is correct
14 Correct 39 ms 79180 KB Output is correct
15 Correct 39 ms 78864 KB Output is correct
16 Correct 41 ms 79096 KB Output is correct
17 Correct 45 ms 79104 KB Output is correct
18 Correct 37 ms 78752 KB Output is correct
19 Correct 38 ms 78976 KB Output is correct
20 Correct 39 ms 79024 KB Output is correct
21 Correct 463 ms 104432 KB Output is correct
22 Correct 207 ms 91144 KB Output is correct
23 Correct 550 ms 110476 KB Output is correct
24 Correct 284 ms 95724 KB Output is correct
25 Correct 1667 ms 156952 KB Output is correct
26 Correct 1423 ms 150588 KB Output is correct
27 Correct 790 ms 138516 KB Output is correct
28 Correct 1317 ms 138076 KB Output is correct
29 Correct 1298 ms 138220 KB Output is correct
30 Correct 901 ms 124360 KB Output is correct
31 Correct 561 ms 111464 KB Output is correct
32 Correct 429 ms 111816 KB Output is correct
33 Correct 440 ms 110388 KB Output is correct
34 Correct 978 ms 128072 KB Output is correct
35 Correct 732 ms 117492 KB Output is correct
36 Correct 789 ms 122912 KB Output is correct
37 Correct 796 ms 130552 KB Output is correct
38 Correct 818 ms 143176 KB Output is correct
39 Correct 519 ms 121036 KB Output is correct
40 Correct 1336 ms 139432 KB Output is correct
41 Correct 1346 ms 139692 KB Output is correct
42 Correct 1419 ms 143276 KB Output is correct
43 Correct 581 ms 112460 KB Output is correct
44 Correct 1006 ms 131812 KB Output is correct
45 Correct 1027 ms 127996 KB Output is correct
46 Correct 927 ms 128248 KB Output is correct
47 Correct 800 ms 127496 KB Output is correct
48 Correct 1716 ms 162444 KB Output is correct