Submission #807335

#	Time	Username	Problem	Language	Result	Execution time	Memory
807335		caganyanmaz	Robot (JOI21_ho_t4)	C++17	0 / 100	449 ms	67324 KiB

Main

#include <bits/stdc++.h>
#define s second
#define mt(x...) array<int, 3>({x})
#define pb push_back
using namespace std;

constexpr static int MXSIZE = 2e5;
constexpr static int MXST = 1e7;


int get(int l, int r, int index, int i);
int update(int l, int r, int index, int i, int val);
int build(int l, int r);
map<int, array<int, 2>> calculate_changes(int node, int current);


int nxt, n, m, bt[MXST], p[MXSIZE], c[MXSIZE], ll[MXST], rr[MXST];
vector<array<int, 3>> g[MXSIZE];
vector<int> edges[MXSIZE];
bitset<MXSIZE> visited;


int main()
{
        cin >> n >> m;
        for (int i = 0; i < m; i++)
        {
                int a, b, _c, _p;
                cin >> a >> b >> _c >> _p;
                a--, b--;
                g[a].pb({b, _c, i});
                g[b].pb({a, _c, i});
                edges[a].pb(i);
                edges[b].pb(i);
                p[i] = _p;
                c[i] = _c;
        }
        int root = build(0, m);
        priority_queue<array<int, 3>> pq; // Cost, current node, last values
        pq.push({0, 0, root});
        while (pq.size())
        {
                auto [cost, node, current] = pq.top();
                pq.pop();
                if (visited[node])
                        continue;
                if (node == n-1)
                {
                        cout << (-cost) << "\n";
                        return 0;
                }
                visited[node] = true;
                map<int, array<int, 2>> changes = calculate_changes(node, current); // O(M logN)
                for (auto [nn, _c, ee] : g[node])
                {
                        if (visited[nn])
                                continue;
                        if (changes.find(_c) == changes.end())
                        {
                                pq.push({cost, nn, current});
                        }
                        else
                        {
                                auto [tt, nc] = changes[_c];
                                int ccc = get(0, m, current, ee);
                                if (tt > ccc)
                                {
                                        nc = update(0, m, current, ee,0);
                                        pq.push({cost - ccc, nn, nc});
                                }
                                else
                                {
                                        pq.push({cost - tt, nn, nc});
                                }
                        }
                }
        }
        cout << "-1\n";
}

map<int, array<int, 2>> calculate_changes(int node, int current)
{
        map<int, array<int, 2>> costs; // Color type, total cost, max, cost
        vector<int> cc(edges[node].size());
        for (int i = 0; i < cc.size(); i++)
                cc[i] = get(0, m, current, edges[node][i]);

        for (int j = 0; j < edges[node].size(); j++)
        {
                int i = edges[node][j];
                auto it = costs.find(c[i]);
                if (it != costs.end())
                {
                        int total_cost = (it->s)[0] + cc[j];
                        int mx_cost = (it->s)[1];
                        if (mx_cost == -1 || cc[mx_cost] < cc[j])
                                mx_cost = j;
                        costs[c[i]] = {total_cost, mx_cost};
                }
                else
                {
                        costs[c[i]] = {cc[j], j};
                }

        }
        map<int, array<int, 2>> res; // Color type, additional cost, new value
        for (int j = 0; j < edges[node].size(); j++)
        {
                int i = edges[node][j];
                if (costs[c[i]][1] == j)
                        continue;
                int cost_add, new_c;
                if (res.find(c[i]) != res.end())
                {
                        auto [ca, nc] = res[c[i]];
                        cost_add = ca;
                        new_c = nc;
                }
                else
                {
                        cost_add = 0;
                        new_c = current;
                }
                cost_add += cc[j];
                new_c = update(0, m, new_c, i, 0);
                res[c[i]] = {cost_add, new_c};
        }
        return res;

}

int build(int l, int r)
{
        if (r - l == 1)
        {
                bt[nxt] = p[l];
                return nxt++;
        }
        int m = l+r>>1;
        int lnode = build(l, m);
        int rnode = build(m, r);
        ll[nxt] = lnode;
        rr[nxt] = rnode;
        return nxt++;
}
int update(int l, int r, int index, int i, int val)
{
        if (r - l == 1)
        {
                bt[nxt] = val;
                return nxt++;
        }
        int m = l+r>>1;
        int lnode = ll[index], rnode = rr[index];
        if (i < m)
                lnode = update(l, m, lnode, i, val);
        else
                rnode = update(m, r, rnode, i, val);
        ll[nxt] = lnode;
        rr[nxt] = rnode;
        return nxt++;
}
int get(int l, int r, int index, int i)
{
        if (r - l == 1)
                return bt[index];
        int m = l+r>>1;
        if (i < m)
                return get(l, m, ll[index], i);
        return get(m, r, rr[index], i);
}

Compilation message (stderr)

Main.cpp: In function 'std::map<int, std::array<int, 2> > calculate_changes(int, int)':
Main.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int i = 0; i < cc.size(); i++)
      |                         ~~^~~~~~~~~~~
Main.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int j = 0; j < edges[node].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (int j = 0; j < edges[node].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int build(int, int)':
Main.cpp:139:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         int m = l+r>>1;
      |                 ~^~
Main.cpp: In function 'int update(int, int, int, int, int)':
Main.cpp:153:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |         int m = l+r>>1;
      |                 ~^~
Main.cpp: In function 'int get(int, int, int, int)':
Main.cpp:167:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |         int m = l+r>>1;
      |                 ~^~

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