#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
struct path{
ll s, e, v;
path() {}
path(ll _v, ll _s, ll _e) { s = _s, e = _e, v = _v; }
bool operator< (const path& p) const { return v > p.v; }
};
typedef vector <path> vp;
vp T[303030];
priority_queue <path> Q;
vp K[2020][2020];
vector <pll> V[2020];
bool chk[2020][2];
ll L[101010];
ll n, m, k;
vp add(vp &a, vp &b)
{
vp ret, ans;
ll i, j, c1, c2;
for(auto &p1: a){
for(auto &p2 : b){
if(p1.e != p2.s){
ret.push_back(path(p1.v + p2.v, p1.s, p2.e));
}
}
}
if(!ret.empty()){
sort(ret.begin(), ret.end());
reverse(ret.begin(), ret.end());
ans.push_back(ret[0]);
for(i=1;i<ret.size();i++){
if(ret[i].s != ret[0].s && ret[i].e != ret[0].e) break;
}
if(i < ret.size()){
ans.push_back(ret[i]);
ll s1 = ret[0].s, e1 = ret[i].e;
ll s2 = ret[i].s, e2 = ret[0].e;
ll a;
for(a=1;a<ret.size();a++) if(ret[a].s != s1 && ret[a].e != e1) break;
if(a < ret.size()) ans.push_back(ret[a]);
for(a=1;a<ret.size();a++) if(ret[a].s != s2 && ret[a].e != e2) break;
if(a < ret.size()) ans.push_back(ret[a]);
}
else{
ll a;
ll s = ret[0].s, e = ret[0].e;
for(a=1;a<ret.size();a++) if(ret[a].s != s) break;
if(a < ret.size()) ans.push_back(ret[a]);
for(a=1;a<ret.size();a++) if(ret[a].e != e) break;
if(a < ret.size()) ans.push_back(ret[a]);
}
}
return ans;
}
void dijkstra(ll a, ll b, ll v)
{
path p;
ll i;
chk[a][0] = 1;
Q.push(path(v, a, b));
for(;!Q.empty();){
p = Q.top(); Q.pop();
if(chk[p.e][0] && chk[p.e][1]) continue;
if(chk[p.e][0]) chk[p.e][1] = 1;
else chk[p.e][0] = 1;
K[a][p.e].push_back(path(p.v, b, p.s));
for(pll &j: V[p.e]){
if(!chk[j.first][p.e] && j.first != p.s){
Q.push(path(p.v + j.second, p.e, j.first));
}
}
}
for(i=1;i<=n;i++){
chk[i][0] = chk[i][1] = 0;
}
}
void init_seg(ll p, ll s, ll e)
{
if(s == e){
T[p] = K[L[s]][L[s+1]];
return;
}
init_seg(p<<1, s, (s+e>>1));
init_seg(p<<1|1, (s+e>>1)+1, e);
T[p] = add(T[p<<1], T[p<<1|1]);
}
void update(ll p, ll s, ll e, ll v)
{
if(s == e){
T[p] = K[L[s]][L[s+1]];
return;
}
if(v <= (s+e>>1)) update(p<<1, s, (s+e>>1), v);
else update(p<<1|1, (s+e>>1)+1, e, v);
T[p] = add(T[p<<1], T[p<<1|1]);
}
int main()
{
ll i, j, q, a, b, c;
path p;
scanf("%lld%lld%lld%lld", &n, &m, &q, &k);
for(i=1;i<=m;i++){
scanf("%lld%lld%lld", &a, &b, &c);
V[a].push_back(pll(b, c));
V[b].push_back(pll(a, c));
}
for(i=1;i<=n;i++) for(pll &t: V[i]){
dijkstra(i, t.first, t.second);
}
for(i=1;i<=n;i++) for(j=1;j<=n;j++){
if(!K[i][j].empty()){
vp ret = K[i][j], ans;
ll a;
sort(ret.begin(), ret.end());
reverse(ret.begin(), ret.end());
ans.push_back(ret[0]);
for(a=1;a<ret.size();a++){
if(ret[a].s != ret[0].s && ret[a].e != ret[0].e) break;
}
if(a < ret.size()){
ans.push_back(ret[a]);
ll s1 = ret[0].s, e1 = ret[a].e;
ll s2 = ret[a].s, e2 = ret[0].e;
for(a=1;a<ret.size();a++) if(ret[a].s != s1 && ret[a].e != e1) break;
if(a < ret.size()) ans.push_back(ret[a]);
for(a=1;a<ret.size();a++) if(ret[a].s != s2 && ret[a].e != e2) break;
if(a < ret.size()) ans.push_back(ret[a]);
}
else{
ll s = ret[0].s, e = ret[0].e;
for(a=1;a<ret.size();a++) if(ret[a].s != s) break;
if(a < ret.size()) ans.push_back(ret[a]);
for(a=1;a<ret.size();a++) if(ret[a].e != e) break;
if(a < ret.size()) ans.push_back(ret[a]);
}
K[i][j] = ans;
}
}
for(i=1;i<=k;i++){
scanf("%lld", L+i);
}
init_seg(1, 1, k-1);
for(;q--;){
scanf("%lld%lld", &a, &b);
L[a] = b;
if(a < k) update(1, 1, k-1, a);
if(a > 1) update(1, 1, k-1, a-1);
if(T[1].empty()) printf("-1\n");
else printf("%lld\n", T[1][0].v);
}
return 0;
}
Compilation message
wild_boar.cpp: In function 'vp add(vp&, vp&)':
wild_boar.cpp:44:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=1;i<ret.size();i++){
~^~~~~~~~~~~
wild_boar.cpp:48:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i < ret.size()){
~~^~~~~~~~~~~~
wild_boar.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++) if(ret[a].s != s1 && ret[a].e != e1) break;
~^~~~~~~~~~~
wild_boar.cpp:56:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()) ans.push_back(ret[a]);
~~^~~~~~~~~~~~
wild_boar.cpp:58:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++) if(ret[a].s != s2 && ret[a].e != e2) break;
~^~~~~~~~~~~
wild_boar.cpp:59:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()) ans.push_back(ret[a]);
~~^~~~~~~~~~~~
wild_boar.cpp:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++) if(ret[a].s != s) break;
~^~~~~~~~~~~
wild_boar.cpp:66:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()) ans.push_back(ret[a]);
~~^~~~~~~~~~~~
wild_boar.cpp:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++) if(ret[a].e != e) break;
~^~~~~~~~~~~
wild_boar.cpp:69:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()) ans.push_back(ret[a]);
~~^~~~~~~~~~~~
wild_boar.cpp:28:8: warning: unused variable 'j' [-Wunused-variable]
ll i, j, c1, c2;
^
wild_boar.cpp:28:11: warning: unused variable 'c1' [-Wunused-variable]
ll i, j, c1, c2;
^~
wild_boar.cpp:28:15: warning: unused variable 'c2' [-Wunused-variable]
ll i, j, c1, c2;
^~
wild_boar.cpp: In function 'void init_seg(ll, ll, ll)':
wild_boar.cpp:112:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
init_seg(p<<1, s, (s+e>>1));
~^~
wild_boar.cpp:113:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
init_seg(p<<1|1, (s+e>>1)+1, e);
~^~
wild_boar.cpp: In function 'void update(ll, ll, ll, ll)':
wild_boar.cpp:125:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
if(v <= (s+e>>1)) update(p<<1, s, (s+e>>1), v);
~^~
wild_boar.cpp:125:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
if(v <= (s+e>>1)) update(p<<1, s, (s+e>>1), v);
~^~
wild_boar.cpp:126:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
else update(p<<1|1, (s+e>>1)+1, e, v);
~^~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:158:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++){
~^~~~~~~~~~~
wild_boar.cpp:162:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()){
~~^~~~~~~~~~~~
wild_boar.cpp:168:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++) if(ret[a].s != s1 && ret[a].e != e1) break;
~^~~~~~~~~~~
wild_boar.cpp:169:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()) ans.push_back(ret[a]);
~~^~~~~~~~~~~~
wild_boar.cpp:171:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++) if(ret[a].s != s2 && ret[a].e != e2) break;
~^~~~~~~~~~~
wild_boar.cpp:172:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()) ans.push_back(ret[a]);
~~^~~~~~~~~~~~
wild_boar.cpp:177:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++) if(ret[a].s != s) break;
~^~~~~~~~~~~
wild_boar.cpp:178:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()) ans.push_back(ret[a]);
~~^~~~~~~~~~~~
wild_boar.cpp:180:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(a=1;a<ret.size();a++) if(ret[a].e != e) break;
~^~~~~~~~~~~
wild_boar.cpp:181:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a < ret.size()) ans.push_back(ret[a]);
~~^~~~~~~~~~~~
wild_boar.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld", &n, &m, &q, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", L+i);
~~~~~^~~~~~~~~~~~~
wild_boar.cpp:195:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
103416 KB |
Output is correct |
| 2 |
Correct |
87 ms |
103496 KB |
Output is correct |
| 3 |
Correct |
106 ms |
103708 KB |
Output is correct |
| 4 |
Correct |
90 ms |
103708 KB |
Output is correct |
| 5 |
Correct |
92 ms |
103708 KB |
Output is correct |
| 6 |
Correct |
111 ms |
103708 KB |
Output is correct |
| 7 |
Correct |
104 ms |
103708 KB |
Output is correct |
| 8 |
Correct |
91 ms |
103708 KB |
Output is correct |
| 9 |
Correct |
95 ms |
103728 KB |
Output is correct |
| 10 |
Incorrect |
91 ms |
103728 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
103416 KB |
Output is correct |
| 2 |
Correct |
87 ms |
103496 KB |
Output is correct |
| 3 |
Correct |
106 ms |
103708 KB |
Output is correct |
| 4 |
Correct |
90 ms |
103708 KB |
Output is correct |
| 5 |
Correct |
92 ms |
103708 KB |
Output is correct |
| 6 |
Correct |
111 ms |
103708 KB |
Output is correct |
| 7 |
Correct |
104 ms |
103708 KB |
Output is correct |
| 8 |
Correct |
91 ms |
103708 KB |
Output is correct |
| 9 |
Correct |
95 ms |
103728 KB |
Output is correct |
| 10 |
Incorrect |
91 ms |
103728 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
103416 KB |
Output is correct |
| 2 |
Correct |
87 ms |
103496 KB |
Output is correct |
| 3 |
Correct |
106 ms |
103708 KB |
Output is correct |
| 4 |
Correct |
90 ms |
103708 KB |
Output is correct |
| 5 |
Correct |
92 ms |
103708 KB |
Output is correct |
| 6 |
Correct |
111 ms |
103708 KB |
Output is correct |
| 7 |
Correct |
104 ms |
103708 KB |
Output is correct |
| 8 |
Correct |
91 ms |
103708 KB |
Output is correct |
| 9 |
Correct |
95 ms |
103728 KB |
Output is correct |
| 10 |
Incorrect |
91 ms |
103728 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
103416 KB |
Output is correct |
| 2 |
Correct |
87 ms |
103496 KB |
Output is correct |
| 3 |
Correct |
106 ms |
103708 KB |
Output is correct |
| 4 |
Correct |
90 ms |
103708 KB |
Output is correct |
| 5 |
Correct |
92 ms |
103708 KB |
Output is correct |
| 6 |
Correct |
111 ms |
103708 KB |
Output is correct |
| 7 |
Correct |
104 ms |
103708 KB |
Output is correct |
| 8 |
Correct |
91 ms |
103708 KB |
Output is correct |
| 9 |
Correct |
95 ms |
103728 KB |
Output is correct |
| 10 |
Incorrect |
91 ms |
103728 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
