#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
int N,M;
struct edge { int u,v,w; };
vector<edge> edges;
int opp(int a,int b) {
return ((a < 2*M) && (b < 2*M) && ((a^b) == 1));
}
int X[100000];
int num;
vpii adjList[20000];
vi nodes;
int tree[1 << 12];
int build(int s,int e,int i) {
if (s == e) {
tree[i] = num++;
adjList[tree[i]].pb(mp(nodes[s],edges[nodes[s]].w));
return 0;
}
int mid = (s+e) / 2;
build(s,mid,2*i+1),build(mid+1,e,2*i+2);
tree[i] = num++;
adjList[tree[i]].pb(mp(tree[2*i+1],0)),adjList[tree[i]].pb(mp(tree[2*i+2],0));
return 0;
}
int add(int s,int e,int as,int ae,int i,int u) {
if ((s > ae) || (e < as)) return 0;
else if ((s >= as) && (e <= ae)) {
adjList[u].pb(mp(tree[i],0));
return 0;
}
int mid = (s+e) / 2;
add(s,mid,as,ae,2*i+1,u),add(mid+1,e,as,ae,2*i+2,u);
return 0;
}
priority_queue<pair<LLI,int> > H;
LLI dist2[20000];
LLI dist[6000][6000];
struct path { int e,eu,ev; LLI d; };
bool comp(path a,path b) {
return a.d < b.d;
}
vector<path> paths[2001][2001];
int shorten(vector<path> &v) {
int i;
vector<path> v2;
sort(v.begin(),v.end(),comp);
while (!v.empty() && (v.back().d > 1e17)) v.pop_back();
if (v.empty()) return 0;
v2.pb(v[0]);
for (i = 1; i < v.size(); i++) {
if ((v[i].e != v[0].e) && (v[i].ev != v[0].ev)) {
v2.pb(v[i]);
break;
}
}
int m1 = -1,m2 = -1;
for (i = 1; i < v.size(); i++) {
if (v[i].e != v[0].e) {
if (m1 == -1) m1 = i;
else if ((m2 == -1) && (v[i].ev != v[m1].ev)) m2 = i;
}
}
if (m1 != -1) v2.pb(v[m1]),m1 = -1;
if (m2 != -1) v2.pb(v[m2]),m2 = -1;
for (i = 1; i < v.size(); i++) {
if (v[i].ev != v[0].ev) {
if (m1 == -1) m1 = i;
else if ((m2 == -1) && (v[i].e != v[m1].e)) m2 = i;
}
}
if (m1 != -1) v2.pb(v[m1]),m1 = -1;
if (m2 != -1) v2.pb(v[m2]),m2 = -1;
v = v2;
sort(v.begin(),v.end(),comp);
return 0;
}
vector<path> com(vector<path> a,vector<path> b) {
int i,j;
vector<path> c;
for (i = 0; i < a.size(); i++) {
for (j = 0; j < b.size(); j++) {
if (a[i].ev == b[j].eu) c.pb((path){a[i].e,a[i].eu,b[j].ev,min(a[i].d+b[j].d,(LLI) 1e18)});
}
}
shorten(c);
return c;
}
vector<path> tree2[1 << 18];
int build2(int s,int e,int i) {
if (s == e) {
tree2[i] = paths[X[s-1]][X[s]];
return 0;
}
int mid = (s+e) / 2;
build2(s,mid,2*i+1),build2(mid+1,e,2*i+2);
tree2[i] = com(tree2[2*i+1],tree2[2*i+2]);
return 0;
}
int update2(int s,int e,int ai,int i) {
if ((s > ai) || (e < ai)) return 0;
else if (s == e) {
tree2[i] = paths[X[s-1]][X[s]];
return 0;
}
int mid = (s+e) / 2;
update2(s,mid,ai,2*i+1),update2(mid+1,e,ai,2*i+2);
tree2[i] = com(tree2[2*i+1],tree2[2*i+2]);
return 0;
}
vi vv[2001];
int main() {
int i;
int T,L;
int A,B,C,P,Q;
scanf("%d %d %d %d",&N,&M,&T,&L);
for (i = 0; i < M; i++) {
scanf("%d %d %d",&A,&B,&C);
A--,B--;
edges.pb((edge){A,B,C});
edges.pb((edge){B,A,C});
}
for (i = 0; i < L; i++) scanf("%d",&X[i]),X[i]--;
int j,k;
for (i = 0; i < N; i++) edges.pb((edge){N,i,0});
num = edges.size();
for (i = 0; i <= N; i++) {
vi v;
for (j = 0; j < edges.size(); j++) {
if (edges[j].u == i) nodes.pb(j);
if (edges[j].v == i) v.pb(j);
}
build(0,(int) nodes.size()-1,0);
for (j = 0; j < v.size(); j++) {
for (k = 0; k < nodes.size(); k++) {
if (edges[nodes[k]].v == edges[v[j]].u) break;
}
if (k < nodes.size()) {
add(0,(int) nodes.size()-1,0,k-1,0,v[j]);
add(0,(int) nodes.size()-1,k+1,(int) nodes.size()-1,0,v[j]);
}
else add(0,(int) nodes.size()-1,0,(int) nodes.size()-1,0,v[j]);
}
nodes.clear();
}
for (i = 0; i < edges.size(); i++) {
for (j = 0; j < num; j++) dist2[j] = 1e18;
dist2[i] = 0,H.push(mp(0,i));
while (!H.empty()) {
int u = H.top().second;
LLI d = -H.top().first;
H.pop();
if (d > dist2[u]) continue;
for (j = 0; j < adjList[u].size(); j++) {
int v = adjList[u][j].first;
if (d+adjList[u][j].second < dist2[v]) {
dist2[v] = d+adjList[u][j].second;
H.push(mp(-dist2[v],v));
}
}
}
for (j = 0; j < edges.size(); j++) dist[i][j] = dist2[j];
}
for (i = 0; i < edges.size(); i++) vv[edges[i].v].pb(i);
for (i = 0; i < edges.size(); i++) {
for (j = 0; j < edges.size(); j++) {
for (k = 0; k < vv[edges[i].u].size(); k++) {
if (dist[vv[edges[i].u][k]][j] == dist[i][j]+edges[i].w)
paths[edges[i].u][edges[j].v].pb((path){i,vv[edges[i].u][k],j,dist[vv[edges[i].u][k]][j]});
}
//paths[edges[i].v][edges[j].v].pb((path){i,j,dist[i][j]});
}
}
for (i = 0; i <= N; i++) {
for (j = 0; j <= N; j++) shorten(paths[i][j]);
}
build2(1,L-1,0);
for (i = 0; i < T; i++) {
scanf("%d %d",&P,&Q);
P--,Q--;
X[P] = Q;
if (P > 0) update2(1,L-1,P,0);
if (P < L-1) update2(1,L-1,P+1,0);
if (tree2[0].empty()) printf("-1\n");
else printf("%lld\n",(tree2[0][0].d > 1e17) ? -1:tree2[0][0].d);
}
return 0;
}
Compilation message
wild_boar.cpp: In function 'int shorten(std::vector<path>&)':
wild_boar.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 1; i < v.size(); i++) {
~~^~~~~~~~~~
wild_boar.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 1; i < v.size(); i++) {
~~^~~~~~~~~~
wild_boar.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 1; i < v.size(); i++) {
~~^~~~~~~~~~
wild_boar.cpp: In function 'std::vector<path> com(std::vector<path>, std::vector<path>)':
wild_boar.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < a.size(); i++) {
~~^~~~~~~~~~
wild_boar.cpp:91:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < b.size(); j++) {
~~^~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:141:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < edges.size(); j++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:146:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < v.size(); j++) {
~~^~~~~~~~~~
wild_boar.cpp:147:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (k = 0; k < nodes.size(); k++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:150:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (k < nodes.size()) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < edges.size(); i++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:167:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < adjList[u].size(); j++) {
~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:175:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < edges.size(); j++) dist[i][j] = dist2[j];
~~^~~~~~~~~~~~~~
wild_boar.cpp:177:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < edges.size(); i++) vv[edges[i].v].pb(i);
~~^~~~~~~~~~~~~~
wild_boar.cpp:178:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < edges.size(); i++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:179:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < edges.size(); j++) {
~~^~~~~~~~~~~~~~
wild_boar.cpp:180:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (k = 0; k < vv[edges[i].u].size(); k++) {
~~^~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&N,&M,&T,&L);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&A,&B,&C);
~~~~~^~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:134:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < L; i++) scanf("%d",&X[i]),X[i]--;
~~~~~~~~~~~~~~~~~^~~~~~~
wild_boar.cpp:193:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&P,&Q);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
101112 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
101112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
101112 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
101112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
101112 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
101112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
101112 KB |
Output is correct |
| 2 |
Incorrect |
96 ms |
101112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
