#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 4;
vector<int> sack[maxn];
vector<pair<int,int> > ucond[maxn];
int dsu[maxn],uturn[maxn],adjs[maxn];
void join(int u,int v,int w){
if(dsu[u] != dsu[v]){
if(sack[dsu[v]].size() > sack[dsu[u]].size()){
swap(u,v);
}
int temp = dsu[v];
if(uturn[u] == -1 && uturn[temp] != -1){
uturn[u] = w;
}
for(int it : sack[temp]){
sack[dsu[u]].emplace_back(it);
dsu[it] = dsu[u];
ucond[it].emplace_back(dsu[it],w);
}
sack[temp].clear();
}else if(uturn[dsu[u]] == -1){
uturn[dsu[u]] = w;
}
adjs[u]++;
adjs[v]++;
if((adjs[u] > 2 || adjs[v] > 2) && uturn[dsu[u]] == -1){
uturn[dsu[u]] = w;
}
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W){
vector<tuple<int,int,int> > edge;
for(int i=0;i<N;i++){
dsu[i] = i;
uturn[i] = -1;
sack[i].emplace_back(i);
ucond[i].emplace_back(i,0);
}
for(int i=0;i<M;i++){
edge.emplace_back(W[i],U[i],V[i]);
}
sort(edge.begin(),edge.end());
for(auto [w,u,v] : edge){
join(u,v,w);
}
for(int i=0;i<N;i++){
reverse(ucond[i].begin(),ucond[i].end());
}
}
int getMinimumFuelCapacity(int X,int Y){
int msize = min(ucond[X].size(),ucond[Y].size()), best = -1;
for(int i=0;i<msize;i++){
if(ucond[X][i].first == ucond[Y][i].first && uturn[ucond[X][i].first] != -1){
if(best == -1){
best = max({ucond[X][i].second,ucond[Y][i].second,uturn[ucond[X][i].first]});
}else{
best = min(best,max({ucond[X][i].second,ucond[Y][i].second,uturn[ucond[X][i].first]}));
}
}
}
return best;
}
Compilation message
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
46 | for(auto [w,u,v] : edge){
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
6 ms |
9812 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
6 ms |
9832 KB |
Output is correct |
8 |
Correct |
6 ms |
9812 KB |
Output is correct |
9 |
Correct |
122 ms |
26728 KB |
Output is correct |
10 |
Correct |
193 ms |
30276 KB |
Output is correct |
11 |
Correct |
151 ms |
29872 KB |
Output is correct |
12 |
Correct |
170 ms |
31060 KB |
Output is correct |
13 |
Correct |
118 ms |
23616 KB |
Output is correct |
14 |
Correct |
149 ms |
26716 KB |
Output is correct |
15 |
Correct |
226 ms |
32208 KB |
Output is correct |
16 |
Correct |
283 ms |
31584 KB |
Output is correct |
17 |
Correct |
231 ms |
32916 KB |
Output is correct |
18 |
Correct |
189 ms |
25136 KB |
Output is correct |
19 |
Correct |
69 ms |
16140 KB |
Output is correct |
20 |
Correct |
248 ms |
33024 KB |
Output is correct |
21 |
Correct |
239 ms |
32440 KB |
Output is correct |
22 |
Correct |
271 ms |
33684 KB |
Output is correct |
23 |
Correct |
172 ms |
26184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
141 ms |
23000 KB |
Output is correct |
4 |
Correct |
153 ms |
23180 KB |
Output is correct |
5 |
Correct |
190 ms |
23144 KB |
Output is correct |
6 |
Correct |
160 ms |
23128 KB |
Output is correct |
7 |
Correct |
171 ms |
23240 KB |
Output is correct |
8 |
Correct |
166 ms |
22764 KB |
Output is correct |
9 |
Correct |
147 ms |
23044 KB |
Output is correct |
10 |
Correct |
162 ms |
22768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
6 ms |
9812 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
6 ms |
9832 KB |
Output is correct |
8 |
Correct |
6 ms |
9812 KB |
Output is correct |
9 |
Correct |
7 ms |
9676 KB |
Output is correct |
10 |
Correct |
6 ms |
9812 KB |
Output is correct |
11 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9676 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
6 ms |
9812 KB |
Output is correct |
8 |
Correct |
6 ms |
9832 KB |
Output is correct |
9 |
Correct |
6 ms |
9812 KB |
Output is correct |
10 |
Correct |
122 ms |
26728 KB |
Output is correct |
11 |
Correct |
193 ms |
30276 KB |
Output is correct |
12 |
Correct |
151 ms |
29872 KB |
Output is correct |
13 |
Correct |
170 ms |
31060 KB |
Output is correct |
14 |
Correct |
118 ms |
23616 KB |
Output is correct |
15 |
Correct |
6 ms |
9812 KB |
Output is correct |
16 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
6 ms |
9812 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
6 ms |
9832 KB |
Output is correct |
8 |
Correct |
6 ms |
9812 KB |
Output is correct |
9 |
Correct |
122 ms |
26728 KB |
Output is correct |
10 |
Correct |
193 ms |
30276 KB |
Output is correct |
11 |
Correct |
151 ms |
29872 KB |
Output is correct |
12 |
Correct |
170 ms |
31060 KB |
Output is correct |
13 |
Correct |
118 ms |
23616 KB |
Output is correct |
14 |
Correct |
149 ms |
26716 KB |
Output is correct |
15 |
Correct |
226 ms |
32208 KB |
Output is correct |
16 |
Correct |
283 ms |
31584 KB |
Output is correct |
17 |
Correct |
231 ms |
32916 KB |
Output is correct |
18 |
Correct |
189 ms |
25136 KB |
Output is correct |
19 |
Correct |
141 ms |
23000 KB |
Output is correct |
20 |
Correct |
153 ms |
23180 KB |
Output is correct |
21 |
Correct |
190 ms |
23144 KB |
Output is correct |
22 |
Correct |
160 ms |
23128 KB |
Output is correct |
23 |
Correct |
171 ms |
23240 KB |
Output is correct |
24 |
Correct |
166 ms |
22764 KB |
Output is correct |
25 |
Correct |
147 ms |
23044 KB |
Output is correct |
26 |
Correct |
162 ms |
22768 KB |
Output is correct |
27 |
Correct |
6 ms |
9812 KB |
Output is correct |
28 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9676 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
6 ms |
9812 KB |
Output is correct |
8 |
Correct |
6 ms |
9832 KB |
Output is correct |
9 |
Correct |
6 ms |
9812 KB |
Output is correct |
10 |
Correct |
122 ms |
26728 KB |
Output is correct |
11 |
Correct |
193 ms |
30276 KB |
Output is correct |
12 |
Correct |
151 ms |
29872 KB |
Output is correct |
13 |
Correct |
170 ms |
31060 KB |
Output is correct |
14 |
Correct |
118 ms |
23616 KB |
Output is correct |
15 |
Correct |
149 ms |
26716 KB |
Output is correct |
16 |
Correct |
226 ms |
32208 KB |
Output is correct |
17 |
Correct |
283 ms |
31584 KB |
Output is correct |
18 |
Correct |
231 ms |
32916 KB |
Output is correct |
19 |
Correct |
189 ms |
25136 KB |
Output is correct |
20 |
Correct |
141 ms |
23000 KB |
Output is correct |
21 |
Correct |
153 ms |
23180 KB |
Output is correct |
22 |
Correct |
190 ms |
23144 KB |
Output is correct |
23 |
Correct |
160 ms |
23128 KB |
Output is correct |
24 |
Correct |
171 ms |
23240 KB |
Output is correct |
25 |
Correct |
166 ms |
22764 KB |
Output is correct |
26 |
Correct |
147 ms |
23044 KB |
Output is correct |
27 |
Correct |
162 ms |
22768 KB |
Output is correct |
28 |
Correct |
6 ms |
9812 KB |
Output is correct |
29 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |