oj.uz

Submission #602224

# Submission time Handle Problem Language Result Execution time Memory
602224 2022-07-22T17:47:23 Z SamAnd Robot (JOI21_ho_t4) C++17
100 / 100
 1378 ms 83376 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

struct ban
{
    int x, c;
    ll p;
    ban(){}
    ban(int x, int c, ll p)
    {
        this->x = x;
        this->c = c;
        this->p = p;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.p > b.p;
}

bool so(const ban& a, const ban& b)
{
    return a.c < b.c;
}

int n, m;
vector<ban> g[N];

void solv()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int x, y, c, p;
        cin >> x >> y >> c >> p;
        g[x].push_back(ban(y, c, p));
        g[y].push_back(ban(x, c, p));
    }

    map<pair<int, int>, int> mp;
    for (int x = 1; x <= n; ++x)
    {
        sort(all(g[x]), so);
        for (int i = 0; i < g[x].size(); ++i)
        {
            if (i == 0 || g[x][i].c != g[x][i - 1].c)
                mp[m_p(x, g[x][i].c)] = i;
        }
    }

    set<pair<int, int> > c;
    priority_queue<ban> q;
    q.push(ban(1, 0, 0));
    while (1)
    {
        ban t;
        do
        {
            if (q.empty())
            {
                cout << "-1\n";
                return;
            }
            t = q.top();
            q.pop();
        } while (c.find(m_p(t.x, t.c)) != c.end());
        c.insert(m_p(t.x, t.c));
        if (t.x == n && t.c == 0)
        {
            cout << t.p << "\n";
            return;
        }

        if (t.c == 0)
        {
            map<int, ll> s;
            for (int i = 0; i < g[t.x].size(); ++i)
            {
                ban h = g[t.x][i];
                s[g[t.x][i].c] += g[t.x][i].p;
            }

            for (int i = 0; i < g[t.x].size(); ++i)
            {
                ban h = g[t.x][i];
                h.p = t.p;
                q.push(h);
            }
            for (int i = 0; i < g[t.x].size(); ++i)
            {
                ban h = g[t.x][i];
                h.p += t.p;
                h.c = 0;
                q.push(h);
            }
            for (int i = 0; i < g[t.x].size(); ++i)
            {
                ban h = g[t.x][i];
                h.p = t.p;
                h.p += s[g[t.x][i].c] - g[t.x][i].p;
                h.c = 0;
                q.push(h);
            }
        }
        else
        {
            assert(mp.find(m_p(t.x, t.c)) != mp.end());
            ll s = 0;
            for (int i = mp[m_p(t.x, t.c)]; i < g[t.x].size(); ++i)
            {
                ban h = g[t.x][i];
                if (h.c != t.c)
                    break;
                s += h.p;
            }
            for (int i = mp[m_p(t.x, t.c)]; i < g[t.x].size(); ++i)
            {
                ban h = g[t.x][i];
                if (h.c != t.c)
                    break;
                h.p = t.p;
                h.p += s - g[t.x][i].p;
                h.c = 0;
                q.push(h);
            }
        }
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void solv()':
Main.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 0; i < g[x].size(); ++i)
      |                         ~~^~~~~~~~~~~~~
Main.cpp:86:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for (int i = 0; i < g[t.x].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~
Main.cpp:88:21: warning: variable 'h' set but not used [-Wunused-but-set-variable]
   88 |                 ban h = g[t.x][i];
      |                     ^
Main.cpp:92:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for (int i = 0; i < g[t.x].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~
Main.cpp:98:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for (int i = 0; i < g[t.x].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~
Main.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for (int i = 0; i < g[t.x].size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~
Main.cpp:118:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             for (int i = mp[m_p(t.x, t.c)]; i < g[t.x].size(); ++i)
      |                                             ~~^~~~~~~~~~~~~~~
Main.cpp:125:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ban>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             for (int i = mp[m_p(t.x, t.c)]; i < g[t.x].size(); ++i)
      |                                             ~~^~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 4 ms 5036 KB Output is correct
6 Correct 3 ms 5032 KB Output is correct
7 Correct 4 ms 5172 KB Output is correct
8 Correct 3 ms 5040 KB Output is correct
9 Correct 8 ms 5588 KB Output is correct
10 Correct 7 ms 5480 KB Output is correct
11 Correct 7 ms 5588 KB Output is correct
12 Correct 6 ms 5424 KB Output is correct
13 Correct 6 ms 5588 KB Output is correct
14 Correct 6 ms 5548 KB Output is correct
15 Correct 6 ms 5204 KB Output is correct
16 Correct 8 ms 5344 KB Output is correct
17 Correct 7 ms 5372 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 5 ms 5428 KB Output is correct
20 Correct 5 ms 5204 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 24940 KB Output is correct
2 Correct 135 ms 14020 KB Output is correct
3 Correct 105 ms 20412 KB Output is correct
4 Correct 106 ms 16824 KB Output is correct
5 Correct 1195 ms 62568 KB Output is correct
6 Correct 930 ms 54880 KB Output is correct
7 Correct 520 ms 47376 KB Output is correct
8 Correct 692 ms 34524 KB Output is correct
9 Correct 891 ms 34608 KB Output is correct
10 Correct 612 ms 32848 KB Output is correct
11 Correct 79 ms 16548 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 4 ms 5036 KB Output is correct
6 Correct 3 ms 5032 KB Output is correct
7 Correct 4 ms 5172 KB Output is correct
8 Correct 3 ms 5040 KB Output is correct
9 Correct 8 ms 5588 KB Output is correct
10 Correct 7 ms 5480 KB Output is correct
11 Correct 7 ms 5588 KB Output is correct
12 Correct 6 ms 5424 KB Output is correct
13 Correct 6 ms 5588 KB Output is correct
14 Correct 6 ms 5548 KB Output is correct
15 Correct 6 ms 5204 KB Output is correct
16 Correct 8 ms 5344 KB Output is correct
17 Correct 7 ms 5372 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 5 ms 5428 KB Output is correct
20 Correct 5 ms 5204 KB Output is correct
21 Correct 346 ms 24940 KB Output is correct
22 Correct 135 ms 14020 KB Output is correct
23 Correct 105 ms 20412 KB Output is correct
24 Correct 106 ms 16824 KB Output is correct
25 Correct 1195 ms 62568 KB Output is correct
26 Correct 930 ms 54880 KB Output is correct
27 Correct 520 ms 47376 KB Output is correct
28 Correct 692 ms 34524 KB Output is correct
29 Correct 891 ms 34608 KB Output is correct
30 Correct 612 ms 32848 KB Output is correct
31 Correct 79 ms 16548 KB Output is correct
32 Correct 189 ms 32084 KB Output is correct
33 Correct 201 ms 32712 KB Output is correct
34 Correct 438 ms 35300 KB Output is correct
35 Correct 276 ms 29396 KB Output is correct
36 Correct 622 ms 45744 KB Output is correct
37 Correct 726 ms 44408 KB Output is correct
38 Correct 612 ms 47128 KB Output is correct
39 Correct 366 ms 35708 KB Output is correct
40 Correct 751 ms 35832 KB Output is correct
41 Correct 1020 ms 36128 KB Output is correct
42 Correct 1335 ms 45276 KB Output is correct
43 Correct 380 ms 27984 KB Output is correct
44 Correct 181 ms 32796 KB Output is correct
45 Correct 717 ms 32220 KB Output is correct
46 Correct 444 ms 31352 KB Output is correct
47 Correct 816 ms 45056 KB Output is correct
48 Correct 1378 ms 83376 KB Output is correct