Submission #602224

#	Time	Username	Problem	Language	Result	Execution time	Memory
602224		SamAnd	Robot (JOI21_ho_t4)	C++17	100 / 100	1378 ms	83376 KiB

Main

#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 (stderr)

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 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42