oj.uz

Submission #243913

# Submission time Handle Problem Language Result Execution time Memory
243913 2020-07-02T07:12:30 Z arnold518 Wild Boar (JOI18_wild_boar) C++14
12 / 100
 843 ms 1014324 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 4000;
const int MAXL = 1e5;
const ll INF = 4e18;

struct Edge
{
	int u, v, w, p;
};

int N, M, T, L;
vector<Edge> adj[MAXN+10], radj[MAXN+10];
Edge E[MAXN+10];
ll dist[MAXN+10][MAXN+10];
int A[MAXN+10];

struct Queue
{
	int v; ll w;
	bool operator < (const Queue &p) const { return w>p.w; }
};

struct Node
{
	int l, r; ll w;
	Node() : l(0), r(0), w(INF) {}
	Node(int l, int r, ll w) : l(l), r(r), w(w) {}
	bool operator < (const Node &p) const { return w<p.w; }
};

Node dist2[MAXN+10][MAXN+10][4];
Node tree[MAXN*4+10][4];

void add(int node)
{
	int i, j, k;
	for(i=0; i<4; i++) tree[node][i]=Node();

	vector<Node> V;
	for(i=0; i<4; i++) for(j=0; j<4; j++) if(tree[node*2][i].r!=tree[node*2+1][j].l) V.push_back({tree[node*2][i].l, tree[node*2+1][j].r, tree[node*2][i].w+tree[node*2+1][j].w});

	for(i=0; i<V.size(); i++) tree[node][0]=min(tree[node][0], V[i]);
	for(i=0; i<V.size(); i++) if(V[i].l!=tree[node][0].l && V[i].r!=tree[node][0].r) tree[node][1]=min(tree[node][1], V[i]);
	for(i=0; i<V.size(); i++) if(V[i].l!=tree[node][0].l && V[i].r!=tree[node][1].r) tree[node][2]=min(tree[node][2], V[i]);
	for(i=0; i<V.size(); i++) if(V[i].l!=tree[node][1].l && V[i].r!=tree[node][0].r) tree[node][3]=min(tree[node][3], V[i]);
}

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		int i, j;
		for(i=0; i<4; i++) tree[node][i]=dist2[A[tl]][A[tl+1]][i];
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	add(node);
}

void update(int node, int tl, int tr, int p)
{
	if(tr<p-1 || p<tl) return;
	if(tl==tr)
	{
		int i, j;
		for(i=0; i<4; i++) tree[node][i]=dist2[A[tl]][A[tl+1]][i];
		return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, p);
	update(node*2+1, mid+1, tr, p);
	add(node);
}

int main()
{
	int i, j, k;
	scanf("%d%d%d%d", &N, &M, &T, &L);
	for(i=1; i<=M; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back({u, v, w, i*2-1}); radj[v].push_back({u, v, w, i*2-1});
		adj[v].push_back({v, u, w, i*2}); radj[u].push_back({v, u, w, i*2});
		E[i*2-1]={u, v, w, i*2-1};
		E[i*2]={v, u, w, i*2};
	}
	for(i=1; i<=N; i++) sort(adj[i].begin(), adj[i].end(), [&](const Edge &p, const Edge &q) { return p.v<q.v; });

	for(i=1; i<=2*M; i++)
	{
		for(j=1; j<=2*M; j++) dist[i][j]=INF;

		priority_queue<Queue> PQ;
		PQ.push({i, E[i].w});
		while(!PQ.empty())
		{
			Queue now=PQ.top(); PQ.pop();
			if(dist[i][now.v]<=now.w) continue;
			dist[i][now.v]=now.w;
			for(auto nxt : adj[E[now.v].v]) if(nxt.v!=E[now.v].u) PQ.push({nxt.p, now.w+nxt.w});
		}
	}

	for(i=1; i<=N; i++)
	{
		for(j=1; j<=N; j++)
		{
			vector<Node> V;
			for(k=0; k<4; k++) dist2[i][j][k]=Node();
			for(auto it : adj[i]) for(auto jt : radj[j]) V.push_back(Node(it.v, jt.u, dist[it.p][jt.p]));

			for(k=0; k<V.size(); k++) dist2[i][j][0]=min(dist2[i][j][0], V[k]);
			for(k=0; k<V.size(); k++) if(V[k].l!=dist2[i][j][0].l && V[k].r!=dist2[i][j][0].r) dist2[i][j][1]=min(dist2[i][j][1], V[k]);
			for(k=0; k<V.size(); k++) if(V[k].l!=dist2[i][j][0].l && V[k].r!=dist2[i][j][1].r) dist2[i][j][2]=min(dist2[i][j][2], V[k]);
			for(k=0; k<V.size(); k++) if(V[k].l!=dist2[i][j][1].l && V[k].r!=dist2[i][j][0].r) dist2[i][j][3]=min(dist2[i][j][3], V[k]);
		}
	}

	//for(i=1; i<=2*M; i++) { for(j=1; j<=2*M; j++) printf("%lld ", dist[i][j]); printf("\n"); }

	//for(i=1; i<=N; i++) { for(j=1; j<=N; j++) { for(k=0; k<4; k++) printf("%lld ", dist2[i][j][k].w); printf(" / "); } printf("\n"); }

	for(i=1; i<=L; i++) scanf("%d", &A[i]);
	init(1, 1, L-1);

	while(T--)
	{
		int p, q;
		scanf("%d%d", &p, &q); A[p]=q;
		update(1, 1, L-1, p);
		if(tree[1][0].w==INF) printf("-1\n");
		else printf("%lld\n", tree[1][0].w);
	}
}

Compilation message

wild_boar.cpp: In function 'void add(int)':
wild_boar.cpp:48:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size(); i++) tree[node][0]=min(tree[node][0], V[i]);
           ~^~~~~~~~~
wild_boar.cpp:49:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size(); i++) if(V[i].l!=tree[node][0].l && V[i].r!=tree[node][0].r) tree[node][1]=min(tree[node][1], V[i]);
           ~^~~~~~~~~
wild_boar.cpp:50:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size(); i++) if(V[i].l!=tree[node][0].l && V[i].r!=tree[node][1].r) tree[node][2]=min(tree[node][2], V[i]);
           ~^~~~~~~~~
wild_boar.cpp:51:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size(); i++) if(V[i].l!=tree[node][1].l && V[i].r!=tree[node][0].r) tree[node][3]=min(tree[node][3], V[i]);
           ~^~~~~~~~~
wild_boar.cpp:42:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
wild_boar.cpp: In function 'void init(int, int, int)':
wild_boar.cpp:58:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
wild_boar.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wild_boar.cpp: In function 'void update(int, int, int, int)':
wild_boar.cpp:73:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
wild_boar.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:121:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(k=0; k<V.size(); k++) dist2[i][j][0]=min(dist2[i][j][0], V[k]);
             ~^~~~~~~~~
wild_boar.cpp:122:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(k=0; k<V.size(); k++) if(V[k].l!=dist2[i][j][0].l && V[k].r!=dist2[i][j][0].r) dist2[i][j][1]=min(dist2[i][j][1], V[k]);
             ~^~~~~~~~~
wild_boar.cpp:123:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(k=0; k<V.size(); k++) if(V[k].l!=dist2[i][j][0].l && V[k].r!=dist2[i][j][1].r) dist2[i][j][2]=min(dist2[i][j][2], V[k]);
             ~^~~~~~~~~
wild_boar.cpp:124:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(k=0; k<V.size(); k++) if(V[k].l!=dist2[i][j][1].l && V[k].r!=dist2[i][j][0].r) dist2[i][j][3]=min(dist2[i][j][3], V[k]);
             ~^~~~~~~~~
wild_boar.cpp:86:7: 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:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:132:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=L; i++) scanf("%d", &A[i]);
                      ~~~~~^~~~~~~~~~~~~
wild_boar.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &p, &q); A[p]=q;
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1008496 KB Output is correct
2 Correct 544 ms 1008632 KB Output is correct
3 Correct 531 ms 1008632 KB Output is correct
4 Correct 514 ms 1008632 KB Output is correct
5 Correct 523 ms 1008660 KB Output is correct
6 Correct 551 ms 1008632 KB Output is correct
7 Correct 502 ms 1008504 KB Output is correct
8 Correct 530 ms 1008504 KB Output is correct
9 Correct 517 ms 1008504 KB Output is correct
10 Correct 569 ms 1008504 KB Output is correct
11 Correct 550 ms 1008632 KB Output is correct
12 Correct 511 ms 1008504 KB Output is correct
13 Correct 511 ms 1008632 KB Output is correct
14 Correct 535 ms 1008632 KB Output is correct
15 Correct 514 ms 1008632 KB Output is correct
16 Correct 513 ms 1008632 KB Output is correct
17 Correct 528 ms 1008504 KB Output is correct
18 Correct 563 ms 1008504 KB Output is correct
19 Correct 541 ms 1008600 KB Output is correct
20 Correct 563 ms 1008504 KB Output is correct
21 Correct 535 ms 1008632 KB Output is correct
22 Correct 515 ms 1008760 KB Output is correct
23 Correct 549 ms 1008612 KB Output is correct
24 Correct 533 ms 1008632 KB Output is correct
25 Correct 529 ms 1008760 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1008496 KB Output is correct
2 Correct 544 ms 1008632 KB Output is correct
3 Correct 531 ms 1008632 KB Output is correct
4 Correct 514 ms 1008632 KB Output is correct
5 Correct 523 ms 1008660 KB Output is correct
6 Correct 551 ms 1008632 KB Output is correct
7 Correct 502 ms 1008504 KB Output is correct
8 Correct 530 ms 1008504 KB Output is correct
9 Correct 517 ms 1008504 KB Output is correct
10 Correct 569 ms 1008504 KB Output is correct
11 Correct 550 ms 1008632 KB Output is correct
12 Correct 511 ms 1008504 KB Output is correct
13 Correct 511 ms 1008632 KB Output is correct
14 Correct 535 ms 1008632 KB Output is correct
15 Correct 514 ms 1008632 KB Output is correct
16 Correct 513 ms 1008632 KB Output is correct
17 Correct 528 ms 1008504 KB Output is correct
18 Correct 563 ms 1008504 KB Output is correct
19 Correct 541 ms 1008600 KB Output is correct
20 Correct 563 ms 1008504 KB Output is correct
21 Correct 535 ms 1008632 KB Output is correct
22 Correct 515 ms 1008760 KB Output is correct
23 Correct 549 ms 1008612 KB Output is correct
24 Correct 533 ms 1008632 KB Output is correct
25 Correct 529 ms 1008760 KB Output is correct
26 Correct 548 ms 1008988 KB Output is correct
27 Correct 566 ms 1010296 KB Output is correct
28 Correct 567 ms 1010168 KB Output is correct
29 Incorrect 843 ms 1014324 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1008496 KB Output is correct
2 Correct 544 ms 1008632 KB Output is correct
3 Correct 531 ms 1008632 KB Output is correct
4 Correct 514 ms 1008632 KB Output is correct
5 Correct 523 ms 1008660 KB Output is correct
6 Correct 551 ms 1008632 KB Output is correct
7 Correct 502 ms 1008504 KB Output is correct
8 Correct 530 ms 1008504 KB Output is correct
9 Correct 517 ms 1008504 KB Output is correct
10 Correct 569 ms 1008504 KB Output is correct
11 Correct 550 ms 1008632 KB Output is correct
12 Correct 511 ms 1008504 KB Output is correct
13 Correct 511 ms 1008632 KB Output is correct
14 Correct 535 ms 1008632 KB Output is correct
15 Correct 514 ms 1008632 KB Output is correct
16 Correct 513 ms 1008632 KB Output is correct
17 Correct 528 ms 1008504 KB Output is correct
18 Correct 563 ms 1008504 KB Output is correct
19 Correct 541 ms 1008600 KB Output is correct
20 Correct 563 ms 1008504 KB Output is correct
21 Correct 535 ms 1008632 KB Output is correct
22 Correct 515 ms 1008760 KB Output is correct
23 Correct 549 ms 1008612 KB Output is correct
24 Correct 533 ms 1008632 KB Output is correct
25 Correct 529 ms 1008760 KB Output is correct
26 Correct 548 ms 1008988 KB Output is correct
27 Correct 566 ms 1010296 KB Output is correct
28 Correct 567 ms 1010168 KB Output is correct
29 Incorrect 843 ms 1014324 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1008496 KB Output is correct
2 Correct 544 ms 1008632 KB Output is correct
3 Correct 531 ms 1008632 KB Output is correct
4 Correct 514 ms 1008632 KB Output is correct
5 Correct 523 ms 1008660 KB Output is correct
6 Correct 551 ms 1008632 KB Output is correct
7 Correct 502 ms 1008504 KB Output is correct
8 Correct 530 ms 1008504 KB Output is correct
9 Correct 517 ms 1008504 KB Output is correct
10 Correct 569 ms 1008504 KB Output is correct
11 Correct 550 ms 1008632 KB Output is correct
12 Correct 511 ms 1008504 KB Output is correct
13 Correct 511 ms 1008632 KB Output is correct
14 Correct 535 ms 1008632 KB Output is correct
15 Correct 514 ms 1008632 KB Output is correct
16 Correct 513 ms 1008632 KB Output is correct
17 Correct 528 ms 1008504 KB Output is correct
18 Correct 563 ms 1008504 KB Output is correct
19 Correct 541 ms 1008600 KB Output is correct
20 Correct 563 ms 1008504 KB Output is correct
21 Correct 535 ms 1008632 KB Output is correct
22 Correct 515 ms 1008760 KB Output is correct
23 Correct 549 ms 1008612 KB Output is correct
24 Correct 533 ms 1008632 KB Output is correct
25 Correct 529 ms 1008760 KB Output is correct
26 Correct 548 ms 1008988 KB Output is correct
27 Correct 566 ms 1010296 KB Output is correct
28 Correct 567 ms 1010168 KB Output is correct
29 Incorrect 843 ms 1014324 KB Output isn't correct
30 Halted 0 ms 0 KB -