# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
710465 |
2023-03-15T09:02:31 Z |
Ronin13 |
Robot (JOI21_ho_t4) |
C++14 |
|
1482 ms |
151020 KB |
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1000001;
vector <vector <pll> > g(nmax);
ll d[nmax];
vector <bool> used(nmax);
map <pii, int> mp;
int cnt = 0;
vector <vector <pair<pii, int> > >G(200001);
int m;
void process(vector <pii> cur, int v){
ll s = 0;
vector <int> vv;
for(auto to : cur){
mp[{v, to.s}] = cnt;
vv.pb(cnt++);
vv.pb(cnt++);
s += (ll)to.f;
}
for(int j = 0; j < cur.size(); j++){
int x = vv[j * 2], y = vv[j * 2 + 1];
g[4 * m + v].pb({y, cur[j].f});
g[4 * m + v].pb({x, s - (ll)cur[j].f});
g[x].pb({4 * m + cur[j].s, 0});
g[y].pb({4 * m + cur[j].s, 0});
}
}
void process1(vector <pii> cur, int v){
ll s = 0;
for(int i = 0; i < cur.size(); i++){
s += (ll)cur[i].f;
}
for(int i = 0; i < cur.size(); i++){
int x = mp[{cur[i].s, v}];
x++;
if(i == cur.size() - 1){
if(cur.size() == 1) continue;
int o = cur[cur.size() - 2].s;
int y = mp[{v, o}];
g[x].pb({y, s - (ll)cur[i].f - (ll)cur[i - 1].f});
}
else{
int y = cur.back().s;
y = mp[{v, y}];
g[x].pb({y, s - (ll)cur[i].f - cur.back().f});
}
}
}
int main(){
int n; cin >> n;
cin >> m;
for(int i = 1; i <= m; i++){
int u, v, c, p; cin >> u >> v >> c >> p;
G[u].pb({{c, p}, v});
G[v].pb({{c, p}, u});
}
for(int v = 1; v <= n; v++){
if(G[v].empty()) continue;
sort(G[v].begin(), G[v].end());
vector <pii> cur;
cur.epb(G[v][0].f.s, G[v][0].s);
for(int i = 1; i < G[v].size(); i++){
if(G[v][i].f.f == G[v][i - 1].f.f){
cur.epb(G[v][i].f.s, G[v][i].s);
}
else{
process(cur, v);
cur.clear();
cur.epb(G[v][i].f.s, G[v][i].s);
}
}
process(cur, v);
}
for(int v = 1; v <= n; v++){
if(G[v].empty()) continue;
sort(G[v].begin(), G[v].end());
vector <pii> cur;
cur.epb(G[v][0].f.s, G[v][0].s);
for(int i = 1; i < G[v].size(); i++){
if(G[v][i].f.f == G[v][i - 1].f.f){
cur.epb(G[v][i].f.s, G[v][i].s);
}
else{
process1(cur, v);
cur.clear();
cur.epb(G[v][i].f.s, G[v][i].s);
}
}
process1(cur, v);
}
for(int i = 0; i <= 4 * m + n; i++){
d[i] = 1e18;
}
d[4 * m + 1] = 0;
priority_queue<pll> q;
q.push({0, 4 * m + 1});
while(!q.empty()){
int v = q.top().s;
q.pop();
if(used[v]) continue;
used[v] = true;
for(auto ed : g[v]){
int to = ed.f;
ll len = ed.s;
if(d[to] > d[v] + len){
d[to] = d[v] + len;
q.push({-d[to], to});
}
}
}
if(d[4 * m + n] == 1e18)
cout << -1;
else
cout << d[4 * m + n];
return 0;
}
Compilation message
Main.cpp: In function 'void process(std::vector<std::pair<int, int> >, int)':
Main.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int j = 0; j < cur.size(); j++){
| ~~^~~~~~~~~~~~
Main.cpp: In function 'void process1(std::vector<std::pair<int, int> >, int)':
Main.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i = 0; i < cur.size(); i++){
| ~~^~~~~~~~~~~~
Main.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < cur.size(); i++){
| ~~^~~~~~~~~~~~
Main.cpp:46:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | if(i == cur.size() - 1){
| ~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 1; i < G[v].size(); i++){
| ~~^~~~~~~~~~~~~
Main.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 1; i < G[v].size(); i++){
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
28500 KB |
Output is correct |
2 |
Correct |
15 ms |
28632 KB |
Output is correct |
3 |
Correct |
14 ms |
28536 KB |
Output is correct |
4 |
Correct |
15 ms |
28500 KB |
Output is correct |
5 |
Correct |
14 ms |
28628 KB |
Output is correct |
6 |
Correct |
13 ms |
28644 KB |
Output is correct |
7 |
Correct |
17 ms |
29072 KB |
Output is correct |
8 |
Correct |
16 ms |
28896 KB |
Output is correct |
9 |
Correct |
20 ms |
29652 KB |
Output is correct |
10 |
Correct |
20 ms |
29720 KB |
Output is correct |
11 |
Correct |
19 ms |
29788 KB |
Output is correct |
12 |
Correct |
18 ms |
29460 KB |
Output is correct |
13 |
Correct |
19 ms |
29704 KB |
Output is correct |
14 |
Correct |
18 ms |
29700 KB |
Output is correct |
15 |
Correct |
16 ms |
29080 KB |
Output is correct |
16 |
Correct |
20 ms |
29660 KB |
Output is correct |
17 |
Correct |
19 ms |
29396 KB |
Output is correct |
18 |
Correct |
15 ms |
28800 KB |
Output is correct |
19 |
Correct |
19 ms |
29908 KB |
Output is correct |
20 |
Correct |
19 ms |
29268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
523 ms |
71176 KB |
Output is correct |
2 |
Correct |
184 ms |
47248 KB |
Output is correct |
3 |
Correct |
767 ms |
103428 KB |
Output is correct |
4 |
Correct |
326 ms |
56004 KB |
Output is correct |
5 |
Correct |
1152 ms |
135940 KB |
Output is correct |
6 |
Correct |
1137 ms |
133124 KB |
Output is correct |
7 |
Correct |
741 ms |
144784 KB |
Output is correct |
8 |
Correct |
1336 ms |
131248 KB |
Output is correct |
9 |
Correct |
1391 ms |
131444 KB |
Output is correct |
10 |
Correct |
737 ms |
92320 KB |
Output is correct |
11 |
Correct |
517 ms |
77376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
28500 KB |
Output is correct |
2 |
Correct |
15 ms |
28632 KB |
Output is correct |
3 |
Correct |
14 ms |
28536 KB |
Output is correct |
4 |
Correct |
15 ms |
28500 KB |
Output is correct |
5 |
Correct |
14 ms |
28628 KB |
Output is correct |
6 |
Correct |
13 ms |
28644 KB |
Output is correct |
7 |
Correct |
17 ms |
29072 KB |
Output is correct |
8 |
Correct |
16 ms |
28896 KB |
Output is correct |
9 |
Correct |
20 ms |
29652 KB |
Output is correct |
10 |
Correct |
20 ms |
29720 KB |
Output is correct |
11 |
Correct |
19 ms |
29788 KB |
Output is correct |
12 |
Correct |
18 ms |
29460 KB |
Output is correct |
13 |
Correct |
19 ms |
29704 KB |
Output is correct |
14 |
Correct |
18 ms |
29700 KB |
Output is correct |
15 |
Correct |
16 ms |
29080 KB |
Output is correct |
16 |
Correct |
20 ms |
29660 KB |
Output is correct |
17 |
Correct |
19 ms |
29396 KB |
Output is correct |
18 |
Correct |
15 ms |
28800 KB |
Output is correct |
19 |
Correct |
19 ms |
29908 KB |
Output is correct |
20 |
Correct |
19 ms |
29268 KB |
Output is correct |
21 |
Correct |
523 ms |
71176 KB |
Output is correct |
22 |
Correct |
184 ms |
47248 KB |
Output is correct |
23 |
Correct |
767 ms |
103428 KB |
Output is correct |
24 |
Correct |
326 ms |
56004 KB |
Output is correct |
25 |
Correct |
1152 ms |
135940 KB |
Output is correct |
26 |
Correct |
1137 ms |
133124 KB |
Output is correct |
27 |
Correct |
741 ms |
144784 KB |
Output is correct |
28 |
Correct |
1336 ms |
131248 KB |
Output is correct |
29 |
Correct |
1391 ms |
131444 KB |
Output is correct |
30 |
Correct |
737 ms |
92320 KB |
Output is correct |
31 |
Correct |
517 ms |
77376 KB |
Output is correct |
32 |
Correct |
1002 ms |
120096 KB |
Output is correct |
33 |
Correct |
873 ms |
95132 KB |
Output is correct |
34 |
Correct |
1061 ms |
108004 KB |
Output is correct |
35 |
Correct |
917 ms |
95816 KB |
Output is correct |
36 |
Correct |
776 ms |
100580 KB |
Output is correct |
37 |
Correct |
861 ms |
120240 KB |
Output is correct |
38 |
Correct |
772 ms |
144236 KB |
Output is correct |
39 |
Correct |
1199 ms |
131804 KB |
Output is correct |
40 |
Correct |
1450 ms |
132624 KB |
Output is correct |
41 |
Correct |
1482 ms |
132984 KB |
Output is correct |
42 |
Correct |
1308 ms |
126904 KB |
Output is correct |
43 |
Correct |
636 ms |
81216 KB |
Output is correct |
44 |
Correct |
1437 ms |
151020 KB |
Output is correct |
45 |
Correct |
962 ms |
106332 KB |
Output is correct |
46 |
Correct |
848 ms |
100300 KB |
Output is correct |
47 |
Correct |
932 ms |
112824 KB |
Output is correct |
48 |
Correct |
1347 ms |
141088 KB |
Output is correct |