# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
371267 |
2021-02-26T10:13:29 Z |
arnold518 |
Robot (JOI21_ho_t4) |
C++14 |
|
2332 ms |
297376 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 4e5;
const int MAXM = 2e6;
const ll INF = 1e18;
struct Edge
{
int u, v, c, p, q;
};
int N, M;
Edge E[MAXN+10];
vector<Edge> adj[MAXN+10], radj[MAXN+10];
map<int, ll> MM[MAXN+10];
vector<int> VV[MAXN+10];
map<int, pii> M2[MAXN+10];
int ncnt=0;
vector<pll> adj2[MAXM+10];
ll dist[MAXM+10];
struct Queue
{
int u; ll w;
bool operator < (const Queue &p) const
{
return w>p.w;
}
};
vector<Edge> V[MAXN+10];
int main()
{
scanf("%d%d", &N, &M);
for(int i=1; i<=M; i++)
{
int u, v, c, p;
scanf("%d%d%d%d", &u, &v, &c, &p);
adj[u].push_back({u, v, c, p, i*2-1});
adj[v].push_back({v, u, c, p, i*2});
radj[u].push_back({v, u, c, p, i*2});
radj[v].push_back({u, v, c, p, i*2-1});
E[i*2-1]={u, v, c, p, i*2-1};
E[i*2]={v, u, c, p, i*2};
MM[u][c]+=p;
MM[v][c]+=p;
}
ncnt=M*2*2;
for(int i=1; i<=N; i++)
{
{
//+in(0)
int v=++ncnt;
M2[i][0].first=v;
for(auto it : radj[i])
{
int u=it.q;
adj2[u].push_back({v, 0});
}
}
{
//-in(0)
int v=++ncnt;
M2[i][0].second=v;
for(auto it : radj[i])
{
int u=it.q+2*M;
adj2[u].push_back({v, 0});
}
}
{
for(auto it : adj[i])
{
V[it.c].push_back(it);
VV[i].push_back(it.c);
}
sort(VV[i].begin(), VV[i].end());
VV[i].erase(unique(VV[i].begin(), VV[i].end()), VV[i].end());
for(auto it : VV[i])
{
int u1=++ncnt, u2=++ncnt;
for(auto jt : V[it])
{
adj2[u1].push_back({jt.q+M*2, jt.p});
adj2[u2].push_back({jt.q, MM[i][it]-jt.p});
}
M2[i][it]={u1, u2};
}
for(auto it : adj[i])
{
V[it.c].clear();
}
}
}
for(int now=1; now<=N; now++)
{
//printf("NOW %d\n", now);
int u1=M2[now][0].first, u2=M2[now][0].second;
//printf("%d %d\n", u1, u2);
for(auto it : VV[now])
{
int v1=M2[now][it].first, v2=M2[now][it].second;
//printf("%d : %d %d\n", it, v1, v2);
adj2[u1].push_back({v1, 0});
adj2[u2].push_back({v1, 0});
adj2[u1].push_back({v2, 0});
adj2[u2].push_back({v2, 0});
}
for(auto nxt : adj[now])
{
int v=M2[nxt.v][nxt.c].second;
adj2[u2].push_back({v, 0});
adj2[u1].push_back({v, 0});
}
}
priority_queue<Queue> PQ;
for(int i=1; i<=ncnt; i++) dist[i]=INF;
PQ.push({M2[1][0].first, 0});
PQ.push({M2[1][0].second, 0});
for(auto it : VV[1])
{
PQ.push({M2[1][it].first, 0});
PQ.push({M2[1][it].second, 0});
}
while(!PQ.empty())
{
Queue now=PQ.top(); PQ.pop();
if(dist[now.u]<=now.w) continue;
//printf("%d %lld\n", now.u, now.w);
dist[now.u]=now.w;
for(auto nxt : adj2[now.u])
{
PQ.push({nxt.first, nxt.second+now.w});
}
}
ll ans=INF;
for(auto nxt : radj[N])
{
//printf("!%d %lld\n", nxt.q, dist[nxt.q]);
//printf("!%d %lld\n", nxt.q+M*2, dist[nxt.q+M*2]);
ans=min(ans, dist[nxt.q]);
ans=min(ans, dist[nxt.q+M*2]);
}
if(ans==INF) ans=-1;
printf("%lld\n", ans);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:151:17: warning: narrowing conversion of 'nxt.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
151 | PQ.push({nxt.first, nxt.second+now.w});
| ~~~~^~~~~
Main.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
43 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%d%d%d%d", &u, &v, &c, &p);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
122476 KB |
Output is correct |
2 |
Correct |
75 ms |
122476 KB |
Output is correct |
3 |
Correct |
75 ms |
122476 KB |
Output is correct |
4 |
Correct |
75 ms |
122476 KB |
Output is correct |
5 |
Correct |
75 ms |
122700 KB |
Output is correct |
6 |
Correct |
78 ms |
122476 KB |
Output is correct |
7 |
Correct |
78 ms |
123304 KB |
Output is correct |
8 |
Correct |
77 ms |
122744 KB |
Output is correct |
9 |
Correct |
83 ms |
124268 KB |
Output is correct |
10 |
Correct |
83 ms |
124268 KB |
Output is correct |
11 |
Correct |
82 ms |
123884 KB |
Output is correct |
12 |
Correct |
82 ms |
123756 KB |
Output is correct |
13 |
Correct |
82 ms |
123884 KB |
Output is correct |
14 |
Correct |
81 ms |
123884 KB |
Output is correct |
15 |
Correct |
79 ms |
123244 KB |
Output is correct |
16 |
Correct |
83 ms |
123756 KB |
Output is correct |
17 |
Correct |
81 ms |
123756 KB |
Output is correct |
18 |
Correct |
77 ms |
123116 KB |
Output is correct |
19 |
Correct |
83 ms |
123804 KB |
Output is correct |
20 |
Correct |
79 ms |
123500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
733 ms |
188628 KB |
Output is correct |
2 |
Correct |
340 ms |
152292 KB |
Output is correct |
3 |
Correct |
930 ms |
208732 KB |
Output is correct |
4 |
Correct |
491 ms |
166116 KB |
Output is correct |
5 |
Correct |
2218 ms |
297376 KB |
Output is correct |
6 |
Correct |
1937 ms |
286516 KB |
Output is correct |
7 |
Correct |
1331 ms |
265672 KB |
Output is correct |
8 |
Correct |
1496 ms |
257004 KB |
Output is correct |
9 |
Correct |
1637 ms |
257132 KB |
Output is correct |
10 |
Correct |
1090 ms |
222180 KB |
Output is correct |
11 |
Correct |
572 ms |
197100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
122476 KB |
Output is correct |
2 |
Correct |
75 ms |
122476 KB |
Output is correct |
3 |
Correct |
75 ms |
122476 KB |
Output is correct |
4 |
Correct |
75 ms |
122476 KB |
Output is correct |
5 |
Correct |
75 ms |
122700 KB |
Output is correct |
6 |
Correct |
78 ms |
122476 KB |
Output is correct |
7 |
Correct |
78 ms |
123304 KB |
Output is correct |
8 |
Correct |
77 ms |
122744 KB |
Output is correct |
9 |
Correct |
83 ms |
124268 KB |
Output is correct |
10 |
Correct |
83 ms |
124268 KB |
Output is correct |
11 |
Correct |
82 ms |
123884 KB |
Output is correct |
12 |
Correct |
82 ms |
123756 KB |
Output is correct |
13 |
Correct |
82 ms |
123884 KB |
Output is correct |
14 |
Correct |
81 ms |
123884 KB |
Output is correct |
15 |
Correct |
79 ms |
123244 KB |
Output is correct |
16 |
Correct |
83 ms |
123756 KB |
Output is correct |
17 |
Correct |
81 ms |
123756 KB |
Output is correct |
18 |
Correct |
77 ms |
123116 KB |
Output is correct |
19 |
Correct |
83 ms |
123804 KB |
Output is correct |
20 |
Correct |
79 ms |
123500 KB |
Output is correct |
21 |
Correct |
733 ms |
188628 KB |
Output is correct |
22 |
Correct |
340 ms |
152292 KB |
Output is correct |
23 |
Correct |
930 ms |
208732 KB |
Output is correct |
24 |
Correct |
491 ms |
166116 KB |
Output is correct |
25 |
Correct |
2218 ms |
297376 KB |
Output is correct |
26 |
Correct |
1937 ms |
286516 KB |
Output is correct |
27 |
Correct |
1331 ms |
265672 KB |
Output is correct |
28 |
Correct |
1496 ms |
257004 KB |
Output is correct |
29 |
Correct |
1637 ms |
257132 KB |
Output is correct |
30 |
Correct |
1090 ms |
222180 KB |
Output is correct |
31 |
Correct |
572 ms |
197100 KB |
Output is correct |
32 |
Correct |
915 ms |
213200 KB |
Output is correct |
33 |
Correct |
860 ms |
194004 KB |
Output is correct |
34 |
Correct |
1510 ms |
230696 KB |
Output is correct |
35 |
Correct |
1147 ms |
211796 KB |
Output is correct |
36 |
Correct |
1147 ms |
221792 KB |
Output is correct |
37 |
Correct |
1313 ms |
243324 KB |
Output is correct |
38 |
Correct |
1318 ms |
265528 KB |
Output is correct |
39 |
Correct |
1096 ms |
225748 KB |
Output is correct |
40 |
Correct |
1509 ms |
257004 KB |
Output is correct |
41 |
Correct |
1656 ms |
257132 KB |
Output is correct |
42 |
Correct |
1789 ms |
266844 KB |
Output is correct |
43 |
Correct |
770 ms |
196444 KB |
Output is correct |
44 |
Correct |
1573 ms |
253520 KB |
Output is correct |
45 |
Correct |
1135 ms |
232044 KB |
Output is correct |
46 |
Correct |
946 ms |
227052 KB |
Output is correct |
47 |
Correct |
1356 ms |
233120 KB |
Output is correct |
48 |
Correct |
2332 ms |
296908 KB |
Output is correct |