# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
855693 |
2023-10-01T16:32:41 Z |
nnhzzz |
Robot (JOI21_ho_t4) |
C++14 |
|
751 ms |
100488 KB |
// cre: Nguyen Ngoc Hung - Train VOI 2024
#include<bits/stdc++.h>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i+=c)
#define int ll
//-------------------------------------------------------------//
const int oo = 1e15,LOG = 20,MAXN = 2e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
int dp[MAXN];
map<int,vpii> adj[MAXN];
map<int,int> dp2[MAXN],sum[MAXN];
void solve(){
int n,m; cin >> n >> m;
REP(i,1,m){
int u,v,c,w; cin >> u >> v >> c >> w;
adj[u][c].emplace_back(v,w);
adj[v][c].emplace_back(u,w);
sum[u][c] += w;
sum[v][c] += w;
}
using T = tuple<int,int,int>;
priority_queue<T,vector<T>,greater<T>> heap;
memset(dp,0x3f3f3f3f,sizeof dp);
dp[1] = 0; heap.emplace(0,1,0);
while(SZ(heap)!=0){
auto [w1,u,col] = heap.top(); heap.pop();
if(col!=0){
if(dp2[u][col]!=w1) continue;
for(auto &[v,cost]:adj[u][col]){
if(mini(dp[v],w1+sum[u][col]-cost)){
heap.emplace(dp[v],v,0);
}
}
}else{
if(dp[u]!=w1) continue;
for(auto &i:adj[u]){
int col = i.fi;
for(auto &[v,cost]:i.se){
if(mini(dp[v],w1+sum[u][col]-cost)) heap.emplace(dp[v],v,0); // ko lat uv
if(mini(dp[v],w1+cost)) heap.emplace(dp[v],v,0); // lat uv
if(dp2[v].count(col)==0){ // lat uv va co dinh mau
int &x = dp2[v][col]; x = w1;
heap.emplace(x,v,col);
}else{
int &x = dp2[v][col];
if(mini(x,w1)){
heap.emplace(x,v,col);
}
}
}
}
}
}
cout << (dp[n]>oo?-1:dp[n]);
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "test"
if(fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
#define name1 "nnhzzz"
if(fopen(name1".inp","r")){
freopen(name1".inp","r",stdin);
freopen(name1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | auto [w1,u,col] = heap.top(); heap.pop();
| ^
Main.cpp:63:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for(auto &[v,cost]:adj[u][col]){
| ^
Main.cpp:72:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | for(auto &[v,cost]:i.se){
| ^
Main.cpp: In function 'int main()':
Main.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen(name1".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | freopen(name1".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
30040 KB |
Output is correct |
2 |
Correct |
7 ms |
30044 KB |
Output is correct |
3 |
Correct |
6 ms |
30148 KB |
Output is correct |
4 |
Correct |
6 ms |
30044 KB |
Output is correct |
5 |
Correct |
7 ms |
30044 KB |
Output is correct |
6 |
Correct |
6 ms |
30044 KB |
Output is correct |
7 |
Correct |
7 ms |
30348 KB |
Output is correct |
8 |
Correct |
6 ms |
30136 KB |
Output is correct |
9 |
Correct |
9 ms |
30812 KB |
Output is correct |
10 |
Correct |
9 ms |
30556 KB |
Output is correct |
11 |
Correct |
8 ms |
30656 KB |
Output is correct |
12 |
Correct |
7 ms |
30556 KB |
Output is correct |
13 |
Correct |
8 ms |
30556 KB |
Output is correct |
14 |
Correct |
9 ms |
30664 KB |
Output is correct |
15 |
Correct |
7 ms |
30300 KB |
Output is correct |
16 |
Correct |
8 ms |
30556 KB |
Output is correct |
17 |
Correct |
8 ms |
30556 KB |
Output is correct |
18 |
Correct |
7 ms |
30300 KB |
Output is correct |
19 |
Correct |
7 ms |
30344 KB |
Output is correct |
20 |
Correct |
7 ms |
30300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
48900 KB |
Output is correct |
2 |
Correct |
55 ms |
40460 KB |
Output is correct |
3 |
Correct |
130 ms |
47820 KB |
Output is correct |
4 |
Correct |
93 ms |
43472 KB |
Output is correct |
5 |
Correct |
733 ms |
98796 KB |
Output is correct |
6 |
Correct |
578 ms |
87696 KB |
Output is correct |
7 |
Correct |
259 ms |
76580 KB |
Output is correct |
8 |
Correct |
281 ms |
65872 KB |
Output is correct |
9 |
Correct |
320 ms |
65872 KB |
Output is correct |
10 |
Correct |
254 ms |
63632 KB |
Output is correct |
11 |
Correct |
98 ms |
47700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
30040 KB |
Output is correct |
2 |
Correct |
7 ms |
30044 KB |
Output is correct |
3 |
Correct |
6 ms |
30148 KB |
Output is correct |
4 |
Correct |
6 ms |
30044 KB |
Output is correct |
5 |
Correct |
7 ms |
30044 KB |
Output is correct |
6 |
Correct |
6 ms |
30044 KB |
Output is correct |
7 |
Correct |
7 ms |
30348 KB |
Output is correct |
8 |
Correct |
6 ms |
30136 KB |
Output is correct |
9 |
Correct |
9 ms |
30812 KB |
Output is correct |
10 |
Correct |
9 ms |
30556 KB |
Output is correct |
11 |
Correct |
8 ms |
30656 KB |
Output is correct |
12 |
Correct |
7 ms |
30556 KB |
Output is correct |
13 |
Correct |
8 ms |
30556 KB |
Output is correct |
14 |
Correct |
9 ms |
30664 KB |
Output is correct |
15 |
Correct |
7 ms |
30300 KB |
Output is correct |
16 |
Correct |
8 ms |
30556 KB |
Output is correct |
17 |
Correct |
8 ms |
30556 KB |
Output is correct |
18 |
Correct |
7 ms |
30300 KB |
Output is correct |
19 |
Correct |
7 ms |
30344 KB |
Output is correct |
20 |
Correct |
7 ms |
30300 KB |
Output is correct |
21 |
Correct |
118 ms |
48900 KB |
Output is correct |
22 |
Correct |
55 ms |
40460 KB |
Output is correct |
23 |
Correct |
130 ms |
47820 KB |
Output is correct |
24 |
Correct |
93 ms |
43472 KB |
Output is correct |
25 |
Correct |
733 ms |
98796 KB |
Output is correct |
26 |
Correct |
578 ms |
87696 KB |
Output is correct |
27 |
Correct |
259 ms |
76580 KB |
Output is correct |
28 |
Correct |
281 ms |
65872 KB |
Output is correct |
29 |
Correct |
320 ms |
65872 KB |
Output is correct |
30 |
Correct |
254 ms |
63632 KB |
Output is correct |
31 |
Correct |
98 ms |
47700 KB |
Output is correct |
32 |
Correct |
89 ms |
44380 KB |
Output is correct |
33 |
Correct |
93 ms |
45764 KB |
Output is correct |
34 |
Correct |
329 ms |
66600 KB |
Output is correct |
35 |
Correct |
230 ms |
57592 KB |
Output is correct |
36 |
Correct |
304 ms |
62472 KB |
Output is correct |
37 |
Correct |
287 ms |
65756 KB |
Output is correct |
38 |
Correct |
292 ms |
75724 KB |
Output is correct |
39 |
Correct |
97 ms |
47900 KB |
Output is correct |
40 |
Correct |
342 ms |
67156 KB |
Output is correct |
41 |
Correct |
350 ms |
67252 KB |
Output is correct |
42 |
Correct |
392 ms |
76600 KB |
Output is correct |
43 |
Correct |
169 ms |
53072 KB |
Output is correct |
44 |
Correct |
268 ms |
58504 KB |
Output is correct |
45 |
Correct |
228 ms |
62548 KB |
Output is correct |
46 |
Correct |
204 ms |
62696 KB |
Output is correct |
47 |
Correct |
248 ms |
66112 KB |
Output is correct |
48 |
Correct |
751 ms |
100488 KB |
Output is correct |