// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FOO(i,a,b) for(int i=(a);i<=int(b);++i)
#define OOF(i,a,b) for(int i=(a);i>=int(b);--i)
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;}
inline ll cdiv(ll x,ll m){return x/m+(x%m?(x<0)^(m>0):0);}
#ifdef OWO
#define safe cerr<<"\033[1;32m"<<__PRETTY_FUNCTION__<<" - "<<__LINE__<<" JIZZ\033[0m\n"
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
#else
#pragma GCC optimize("Ofast")
#define safe ((void)0)
#define debug(...) ((void)0)
#endif
const ll inf = 1e9, INF = 4e18;
const int N = 1e5 + 225;
int n, m, q;
vector<pii> adj[N];
int dis[N], ans[N];
vector<pii> qs[N];
struct dsu{
vector<int> p;
vector<vector<tuple<int, int, int>>> q;
dsu(int n){
p.resize(n + 1); iota(AI(p), 0);
q.resize(n + 1);
FOO(i,1,n) for(auto [v, id]: qs[i])
q[i].pb(i, v, id);
}
int F(int u){ return u == p[u] ? u : p[u] = F(p[u]);}
void M(int a, int b, int w){
a = F(a), b = F(b);
if(a == b) return;
if(q[a].size() < q[b].size()) swap(a, b);
p[b] = a;
for(auto [s, t, id]: q[b]){
if(ans[id]) continue;
if(F(s) == F(t)) ans[id] = w;
else q[a].pb(s, t, id);
}
}
};
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int _ = 0, a, b, w; _ < m; ++_){
cin >> a >> b >> w;
adj[a].pb(b, w);
adj[b].pb(a, w);
}
{ // Dijkstra
priority_queue<pii, vector<pii>, greater<pii>> pq;
auto upd = [&pq](int u, int d){
if(chmin(dis[u], d))
pq.emplace(dis[u], u);
};
fill(dis, dis + n + 1, inf);
int k; cin >> k;
for(int x; k; --k){
cin >> x;
upd(x, 0);
}
while(!pq.empty()){
auto [d, u] = pq.top(); pq.pop();
if(dis[u] < d) continue;
for(auto [v, w]: adj[u])
upd(v, d + w);
}
}
cin >> q;
for(int i = 0, s, t; i < q; ++i){
cin >> s >> t;
qs[s].pb(t, i);
qs[t].pb(s, i);
}
vector<int> ord(n); iota(AI(ord), 1);
sort(AI(ord), [](int a, int b){
return dis[a] > dis[b];
});
dsu D(n + 1);
for(int u: ord){
for(auto [v, _]: adj[u])
if(dis[v] >= dis[u])
D.M(u, v, dis[u]);
}
for(int i = 0; i < q; ++i)
cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5228 KB |
Output is correct |
3 |
Correct |
5 ms |
5228 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5228 KB |
Output is correct |
6 |
Correct |
6 ms |
5228 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5228 KB |
Output is correct |
10 |
Correct |
5 ms |
5228 KB |
Output is correct |
11 |
Correct |
5 ms |
5228 KB |
Output is correct |
12 |
Correct |
5 ms |
5228 KB |
Output is correct |
13 |
Correct |
6 ms |
5228 KB |
Output is correct |
14 |
Correct |
5 ms |
5228 KB |
Output is correct |
15 |
Correct |
5 ms |
5228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5228 KB |
Output is correct |
3 |
Correct |
5 ms |
5228 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5228 KB |
Output is correct |
6 |
Correct |
6 ms |
5228 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5228 KB |
Output is correct |
10 |
Correct |
5 ms |
5228 KB |
Output is correct |
11 |
Correct |
5 ms |
5228 KB |
Output is correct |
12 |
Correct |
5 ms |
5228 KB |
Output is correct |
13 |
Correct |
6 ms |
5228 KB |
Output is correct |
14 |
Correct |
5 ms |
5228 KB |
Output is correct |
15 |
Correct |
5 ms |
5228 KB |
Output is correct |
16 |
Correct |
189 ms |
23480 KB |
Output is correct |
17 |
Correct |
533 ms |
39820 KB |
Output is correct |
18 |
Correct |
35 ms |
8464 KB |
Output is correct |
19 |
Correct |
186 ms |
24404 KB |
Output is correct |
20 |
Correct |
527 ms |
40044 KB |
Output is correct |
21 |
Correct |
293 ms |
30136 KB |
Output is correct |
22 |
Correct |
175 ms |
22632 KB |
Output is correct |
23 |
Correct |
539 ms |
39820 KB |
Output is correct |
24 |
Correct |
553 ms |
39872 KB |
Output is correct |
25 |
Correct |
537 ms |
39836 KB |
Output is correct |
26 |
Correct |
180 ms |
24540 KB |
Output is correct |
27 |
Correct |
182 ms |
24276 KB |
Output is correct |
28 |
Correct |
182 ms |
24152 KB |
Output is correct |
29 |
Correct |
168 ms |
24276 KB |
Output is correct |
30 |
Correct |
176 ms |
24404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
4 ms |
5100 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
4 ms |
5100 KB |
Output is correct |
10 |
Correct |
5 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
194 ms |
18236 KB |
Output is correct |
2 |
Correct |
421 ms |
30296 KB |
Output is correct |
3 |
Correct |
424 ms |
30396 KB |
Output is correct |
4 |
Correct |
84 ms |
13420 KB |
Output is correct |
5 |
Correct |
430 ms |
30492 KB |
Output is correct |
6 |
Correct |
423 ms |
30224 KB |
Output is correct |
7 |
Correct |
444 ms |
30344 KB |
Output is correct |
8 |
Correct |
428 ms |
30348 KB |
Output is correct |
9 |
Correct |
421 ms |
30220 KB |
Output is correct |
10 |
Correct |
417 ms |
30356 KB |
Output is correct |
11 |
Correct |
424 ms |
30220 KB |
Output is correct |
12 |
Correct |
415 ms |
30472 KB |
Output is correct |
13 |
Correct |
415 ms |
30220 KB |
Output is correct |
14 |
Correct |
420 ms |
30336 KB |
Output is correct |
15 |
Correct |
418 ms |
30408 KB |
Output is correct |
16 |
Correct |
427 ms |
30472 KB |
Output is correct |
17 |
Correct |
429 ms |
30712 KB |
Output is correct |
18 |
Correct |
440 ms |
30476 KB |
Output is correct |
19 |
Correct |
84 ms |
13292 KB |
Output is correct |
20 |
Correct |
446 ms |
30352 KB |
Output is correct |
21 |
Correct |
388 ms |
30372 KB |
Output is correct |
22 |
Correct |
98 ms |
14292 KB |
Output is correct |
23 |
Correct |
90 ms |
13992 KB |
Output is correct |
24 |
Correct |
104 ms |
14192 KB |
Output is correct |
25 |
Correct |
103 ms |
14164 KB |
Output is correct |
26 |
Correct |
102 ms |
13988 KB |
Output is correct |
27 |
Correct |
78 ms |
13292 KB |
Output is correct |
28 |
Correct |
101 ms |
14172 KB |
Output is correct |
29 |
Correct |
82 ms |
13420 KB |
Output is correct |
30 |
Correct |
101 ms |
14164 KB |
Output is correct |
31 |
Correct |
84 ms |
13420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5228 KB |
Output is correct |
3 |
Correct |
5 ms |
5228 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5228 KB |
Output is correct |
6 |
Correct |
6 ms |
5228 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
5 ms |
5228 KB |
Output is correct |
10 |
Correct |
5 ms |
5228 KB |
Output is correct |
11 |
Correct |
5 ms |
5228 KB |
Output is correct |
12 |
Correct |
5 ms |
5228 KB |
Output is correct |
13 |
Correct |
6 ms |
5228 KB |
Output is correct |
14 |
Correct |
5 ms |
5228 KB |
Output is correct |
15 |
Correct |
5 ms |
5228 KB |
Output is correct |
16 |
Correct |
189 ms |
23480 KB |
Output is correct |
17 |
Correct |
533 ms |
39820 KB |
Output is correct |
18 |
Correct |
35 ms |
8464 KB |
Output is correct |
19 |
Correct |
186 ms |
24404 KB |
Output is correct |
20 |
Correct |
527 ms |
40044 KB |
Output is correct |
21 |
Correct |
293 ms |
30136 KB |
Output is correct |
22 |
Correct |
175 ms |
22632 KB |
Output is correct |
23 |
Correct |
539 ms |
39820 KB |
Output is correct |
24 |
Correct |
553 ms |
39872 KB |
Output is correct |
25 |
Correct |
537 ms |
39836 KB |
Output is correct |
26 |
Correct |
180 ms |
24540 KB |
Output is correct |
27 |
Correct |
182 ms |
24276 KB |
Output is correct |
28 |
Correct |
182 ms |
24152 KB |
Output is correct |
29 |
Correct |
168 ms |
24276 KB |
Output is correct |
30 |
Correct |
176 ms |
24404 KB |
Output is correct |
31 |
Correct |
4 ms |
5100 KB |
Output is correct |
32 |
Correct |
4 ms |
5100 KB |
Output is correct |
33 |
Correct |
4 ms |
5100 KB |
Output is correct |
34 |
Correct |
4 ms |
5100 KB |
Output is correct |
35 |
Correct |
4 ms |
5100 KB |
Output is correct |
36 |
Correct |
4 ms |
5100 KB |
Output is correct |
37 |
Correct |
4 ms |
5100 KB |
Output is correct |
38 |
Correct |
4 ms |
5100 KB |
Output is correct |
39 |
Correct |
4 ms |
5100 KB |
Output is correct |
40 |
Correct |
5 ms |
5100 KB |
Output is correct |
41 |
Correct |
194 ms |
18236 KB |
Output is correct |
42 |
Correct |
421 ms |
30296 KB |
Output is correct |
43 |
Correct |
424 ms |
30396 KB |
Output is correct |
44 |
Correct |
84 ms |
13420 KB |
Output is correct |
45 |
Correct |
430 ms |
30492 KB |
Output is correct |
46 |
Correct |
423 ms |
30224 KB |
Output is correct |
47 |
Correct |
444 ms |
30344 KB |
Output is correct |
48 |
Correct |
428 ms |
30348 KB |
Output is correct |
49 |
Correct |
421 ms |
30220 KB |
Output is correct |
50 |
Correct |
417 ms |
30356 KB |
Output is correct |
51 |
Correct |
424 ms |
30220 KB |
Output is correct |
52 |
Correct |
415 ms |
30472 KB |
Output is correct |
53 |
Correct |
415 ms |
30220 KB |
Output is correct |
54 |
Correct |
420 ms |
30336 KB |
Output is correct |
55 |
Correct |
418 ms |
30408 KB |
Output is correct |
56 |
Correct |
427 ms |
30472 KB |
Output is correct |
57 |
Correct |
429 ms |
30712 KB |
Output is correct |
58 |
Correct |
440 ms |
30476 KB |
Output is correct |
59 |
Correct |
84 ms |
13292 KB |
Output is correct |
60 |
Correct |
446 ms |
30352 KB |
Output is correct |
61 |
Correct |
388 ms |
30372 KB |
Output is correct |
62 |
Correct |
98 ms |
14292 KB |
Output is correct |
63 |
Correct |
90 ms |
13992 KB |
Output is correct |
64 |
Correct |
104 ms |
14192 KB |
Output is correct |
65 |
Correct |
103 ms |
14164 KB |
Output is correct |
66 |
Correct |
102 ms |
13988 KB |
Output is correct |
67 |
Correct |
78 ms |
13292 KB |
Output is correct |
68 |
Correct |
101 ms |
14172 KB |
Output is correct |
69 |
Correct |
82 ms |
13420 KB |
Output is correct |
70 |
Correct |
101 ms |
14164 KB |
Output is correct |
71 |
Correct |
84 ms |
13420 KB |
Output is correct |
72 |
Correct |
320 ms |
29760 KB |
Output is correct |
73 |
Correct |
534 ms |
39688 KB |
Output is correct |
74 |
Correct |
555 ms |
39688 KB |
Output is correct |
75 |
Correct |
561 ms |
39940 KB |
Output is correct |
76 |
Correct |
543 ms |
39688 KB |
Output is correct |
77 |
Correct |
540 ms |
40000 KB |
Output is correct |
78 |
Correct |
547 ms |
39780 KB |
Output is correct |
79 |
Correct |
552 ms |
39676 KB |
Output is correct |
80 |
Correct |
523 ms |
39684 KB |
Output is correct |
81 |
Correct |
570 ms |
39688 KB |
Output is correct |
82 |
Correct |
539 ms |
39820 KB |
Output is correct |
83 |
Correct |
548 ms |
39692 KB |
Output is correct |
84 |
Correct |
528 ms |
39540 KB |
Output is correct |
85 |
Correct |
527 ms |
39528 KB |
Output is correct |
86 |
Correct |
529 ms |
39428 KB |
Output is correct |
87 |
Correct |
548 ms |
39560 KB |
Output is correct |
88 |
Correct |
539 ms |
39560 KB |
Output is correct |
89 |
Correct |
179 ms |
24548 KB |
Output is correct |
90 |
Correct |
525 ms |
39436 KB |
Output is correct |
91 |
Correct |
531 ms |
39208 KB |
Output is correct |
92 |
Correct |
193 ms |
26196 KB |
Output is correct |
93 |
Correct |
216 ms |
33568 KB |
Output is correct |
94 |
Correct |
189 ms |
26076 KB |
Output is correct |
95 |
Correct |
187 ms |
26196 KB |
Output is correct |
96 |
Correct |
224 ms |
33620 KB |
Output is correct |
97 |
Correct |
204 ms |
24796 KB |
Output is correct |
98 |
Correct |
212 ms |
26076 KB |
Output is correct |
99 |
Correct |
196 ms |
24992 KB |
Output is correct |
100 |
Correct |
191 ms |
26196 KB |
Output is correct |