# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
390301 |
2021-04-15T19:39:52 Z |
oleksg |
Robot (JOI21_ho_t4) |
C++14 |
|
3000 ms |
81404 KB |
#pragma GCC optimize("O2")
#include <fstream>
#include <string>
#include <iostream>
#include <bitset>
#include <math.h>
#include <string>
#include <algorithm>
#include <assert.h>
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include<stdio.h>
#include<ctype.h>
#define ll long long
using namespace std;
ll n, m;
struct con{
ll d;
ll color;
ll cost;
};
vector<con> cons[200001];
map<ll, ll> cost[200001];
// how much to convert all nodes of a color to some other color
map<ll, ll> dist[200001];
map<ll, ll> used[200001];
//if node with color x was used
int main(){
cin >> n >> m;
ll one, two, three, four;
for (int x = 0; x < m; x++){
cin >> one >> two >> three >> four;
cons[one - 1].push_back({two - 1, three, four});
cons[two - 1].push_back({one - 1, three, four});
}
for (int x = 0; x < n; x++){
for (int y = 0; y < cons[x].size(); y++){
ll col = cons[x][y].color;
ll cst = cons[x][y].cost;
if (cost[x].find(col) == cost[x].end()){
cost[x][col] = cst;
} else {
cost[x][col] += cst;
}
}
}
priority_queue<tuple<ll, ll, ll>> q;
//cost, node, color
q.push(make_tuple(0, 0, 0));
while(q.size() > 0){
ll node;
ll cst;
ll color;
tie(cst, node, color) = q.top();
used[node][color] = 1;
q.pop();
cst *= -1;
if (color != 0){
//we need to go to a node with the same color
for (auto con: cons[node]){
if (con.color == color){
if (used[con.d].find(0) == used[con.d].end()){
ll ncost = cst + cost[node][color] - con.cost;
if (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
dist[con.d][0] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
}
}
}
}
else{
//there are 3 things which we can do
for (auto con: cons[node]){
if (used[con.d].find(con.color) == used[con.d].end()){
//dont switch anything and make the next node switch
ll ncost = cst;
if (dist[con.d].find(con.color) == dist[con.d].end() || dist[con.d][con.color] > ncost){
dist[con.d][con.color] = ncost;
q.push(make_tuple(-1 * ncost, con.d, con.color));
}
}
if (used[con.d].find(0) == used[con.d].end()){
//switch everything but the connection
ll ncost = cst + cost[node][con.color] - con.cost;
if (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
dist[con.d][0] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
//switch our node only
ncost = cst + con.cost;
if (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
dist[con.d][0] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
}
}
}
}
if (dist[n - 1].find(0) == dist[n - 1].end()){
cout << -1 << "\n";
}
else{
cout << dist[n - 1][0] << "\n";
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<con>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int y = 0; y < cons[x].size(); y++){
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
33100 KB |
Output is correct |
2 |
Correct |
21 ms |
33176 KB |
Output is correct |
3 |
Correct |
21 ms |
33172 KB |
Output is correct |
4 |
Correct |
21 ms |
33108 KB |
Output is correct |
5 |
Correct |
21 ms |
33100 KB |
Output is correct |
6 |
Correct |
21 ms |
33100 KB |
Output is correct |
7 |
Correct |
22 ms |
33324 KB |
Output is correct |
8 |
Correct |
21 ms |
33220 KB |
Output is correct |
9 |
Correct |
26 ms |
33868 KB |
Output is correct |
10 |
Correct |
26 ms |
33848 KB |
Output is correct |
11 |
Correct |
25 ms |
33612 KB |
Output is correct |
12 |
Correct |
23 ms |
33564 KB |
Output is correct |
13 |
Correct |
25 ms |
33612 KB |
Output is correct |
14 |
Correct |
24 ms |
33616 KB |
Output is correct |
15 |
Correct |
23 ms |
33576 KB |
Output is correct |
16 |
Correct |
25 ms |
33564 KB |
Output is correct |
17 |
Correct |
25 ms |
33624 KB |
Output is correct |
18 |
Correct |
22 ms |
33228 KB |
Output is correct |
19 |
Correct |
25 ms |
33444 KB |
Output is correct |
20 |
Correct |
24 ms |
33484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
318 ms |
56864 KB |
Output is correct |
2 |
Correct |
151 ms |
45308 KB |
Output is correct |
3 |
Correct |
340 ms |
54476 KB |
Output is correct |
4 |
Correct |
203 ms |
49652 KB |
Output is correct |
5 |
Execution timed out |
3072 ms |
81404 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
33100 KB |
Output is correct |
2 |
Correct |
21 ms |
33176 KB |
Output is correct |
3 |
Correct |
21 ms |
33172 KB |
Output is correct |
4 |
Correct |
21 ms |
33108 KB |
Output is correct |
5 |
Correct |
21 ms |
33100 KB |
Output is correct |
6 |
Correct |
21 ms |
33100 KB |
Output is correct |
7 |
Correct |
22 ms |
33324 KB |
Output is correct |
8 |
Correct |
21 ms |
33220 KB |
Output is correct |
9 |
Correct |
26 ms |
33868 KB |
Output is correct |
10 |
Correct |
26 ms |
33848 KB |
Output is correct |
11 |
Correct |
25 ms |
33612 KB |
Output is correct |
12 |
Correct |
23 ms |
33564 KB |
Output is correct |
13 |
Correct |
25 ms |
33612 KB |
Output is correct |
14 |
Correct |
24 ms |
33616 KB |
Output is correct |
15 |
Correct |
23 ms |
33576 KB |
Output is correct |
16 |
Correct |
25 ms |
33564 KB |
Output is correct |
17 |
Correct |
25 ms |
33624 KB |
Output is correct |
18 |
Correct |
22 ms |
33228 KB |
Output is correct |
19 |
Correct |
25 ms |
33444 KB |
Output is correct |
20 |
Correct |
24 ms |
33484 KB |
Output is correct |
21 |
Correct |
318 ms |
56864 KB |
Output is correct |
22 |
Correct |
151 ms |
45308 KB |
Output is correct |
23 |
Correct |
340 ms |
54476 KB |
Output is correct |
24 |
Correct |
203 ms |
49652 KB |
Output is correct |
25 |
Execution timed out |
3072 ms |
81404 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |