| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 807335 |
2023-08-04T16:07:25 Z |
caganyanmaz |
Robot (JOI21_ho_t4) |
C++17 |
|
449 ms |
67324 KB |
#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
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;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9712 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
45152 KB |
Output is correct |
| 2 |
Correct |
66 ms |
22972 KB |
Output is correct |
| 3 |
Correct |
120 ms |
24676 KB |
Output is correct |
| 4 |
Correct |
70 ms |
24580 KB |
Output is correct |
| 5 |
Incorrect |
449 ms |
67324 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9712 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 5 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
9684 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
