oj.uz

Submission #243915

# Submission time Handle Problem Language Result Execution time Memory
243915 2020-07-02T07:15:36 Z arnold518 Wild Boar (JOI18_wild_boar) C++14
47 / 100
 18000 ms 1046632 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[MAXL+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[MAXL*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 593 ms 1032628 KB Output is correct
2 Correct 591 ms 1032724 KB Output is correct
3 Correct 512 ms 1032656 KB Output is correct
4 Correct 588 ms 1032648 KB Output is correct
5 Correct 548 ms 1032696 KB Output is correct
6 Correct 587 ms 1032608 KB Output is correct
7 Correct 643 ms 1032700 KB Output is correct
8 Correct 568 ms 1032696 KB Output is correct
9 Correct 641 ms 1032656 KB Output is correct
10 Correct 637 ms 1032568 KB Output is correct
11 Correct 541 ms 1032592 KB Output is correct
12 Correct 561 ms 1032640 KB Output is correct
13 Correct 570 ms 1032688 KB Output is correct
14 Correct 629 ms 1032632 KB Output is correct
15 Correct 554 ms 1032640 KB Output is correct
16 Correct 558 ms 1032700 KB Output is correct
17 Correct 650 ms 1032696 KB Output is correct
18 Correct 609 ms 1032700 KB Output is correct
19 Correct 542 ms 1032696 KB Output is correct
20 Correct 584 ms 1032952 KB Output is correct
21 Correct 580 ms 1032696 KB Output is correct
22 Correct 539 ms 1032696 KB Output is correct
23 Correct 572 ms 1032696 KB Output is correct
24 Correct 587 ms 1032776 KB Output is correct
25 Correct 532 ms 1032696 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 1032628 KB Output is correct
2 Correct 591 ms 1032724 KB Output is correct
3 Correct 512 ms 1032656 KB Output is correct
4 Correct 588 ms 1032648 KB Output is correct
5 Correct 548 ms 1032696 KB Output is correct
6 Correct 587 ms 1032608 KB Output is correct
7 Correct 643 ms 1032700 KB Output is correct
8 Correct 568 ms 1032696 KB Output is correct
9 Correct 641 ms 1032656 KB Output is correct
10 Correct 637 ms 1032568 KB Output is correct
11 Correct 541 ms 1032592 KB Output is correct
12 Correct 561 ms 1032640 KB Output is correct
13 Correct 570 ms 1032688 KB Output is correct
14 Correct 629 ms 1032632 KB Output is correct
15 Correct 554 ms 1032640 KB Output is correct
16 Correct 558 ms 1032700 KB Output is correct
17 Correct 650 ms 1032696 KB Output is correct
18 Correct 609 ms 1032700 KB Output is correct
19 Correct 542 ms 1032696 KB Output is correct
20 Correct 584 ms 1032952 KB Output is correct
21 Correct 580 ms 1032696 KB Output is correct
22 Correct 539 ms 1032696 KB Output is correct
23 Correct 572 ms 1032696 KB Output is correct
24 Correct 587 ms 1032776 KB Output is correct
25 Correct 532 ms 1032696 KB Output is correct
26 Correct 557 ms 1033124 KB Output is correct
27 Correct 600 ms 1034360 KB Output is correct
28 Correct 573 ms 1034464 KB Output is correct
29 Correct 951 ms 1038584 KB Output is correct
30 Correct 1088 ms 1038712 KB Output is correct
31 Correct 1817 ms 1038736 KB Output is correct
32 Correct 1775 ms 1038912 KB Output is correct
33 Correct 743 ms 1038568 KB Output is correct
34 Correct 784 ms 1038456 KB Output is correct
35 Correct 1577 ms 1038584 KB Output is correct
36 Correct 1299 ms 1038684 KB Output is correct
37 Correct 788 ms 1038360 KB Output is correct
38 Correct 788 ms 1038688 KB Output is correct
39 Correct 930 ms 1038472 KB Output is correct
40 Correct 743 ms 1038600 KB Output is correct
41 Correct 761 ms 1038584 KB Output is correct
42 Correct 873 ms 1038584 KB Output is correct
43 Correct 733 ms 1038476 KB Output is correct
44 Correct 676 ms 1038456 KB Output is correct
45 Correct 667 ms 1038328 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 1032628 KB Output is correct
2 Correct 591 ms 1032724 KB Output is correct
3 Correct 512 ms 1032656 KB Output is correct
4 Correct 588 ms 1032648 KB Output is correct
5 Correct 548 ms 1032696 KB Output is correct
6 Correct 587 ms 1032608 KB Output is correct
7 Correct 643 ms 1032700 KB Output is correct
8 Correct 568 ms 1032696 KB Output is correct
9 Correct 641 ms 1032656 KB Output is correct
10 Correct 637 ms 1032568 KB Output is correct
11 Correct 541 ms 1032592 KB Output is correct
12 Correct 561 ms 1032640 KB Output is correct
13 Correct 570 ms 1032688 KB Output is correct
14 Correct 629 ms 1032632 KB Output is correct
15 Correct 554 ms 1032640 KB Output is correct
16 Correct 558 ms 1032700 KB Output is correct
17 Correct 650 ms 1032696 KB Output is correct
18 Correct 609 ms 1032700 KB Output is correct
19 Correct 542 ms 1032696 KB Output is correct
20 Correct 584 ms 1032952 KB Output is correct
21 Correct 580 ms 1032696 KB Output is correct
22 Correct 539 ms 1032696 KB Output is correct
23 Correct 572 ms 1032696 KB Output is correct
24 Correct 587 ms 1032776 KB Output is correct
25 Correct 532 ms 1032696 KB Output is correct
26 Correct 557 ms 1033124 KB Output is correct
27 Correct 600 ms 1034360 KB Output is correct
28 Correct 573 ms 1034464 KB Output is correct
29 Correct 951 ms 1038584 KB Output is correct
30 Correct 1088 ms 1038712 KB Output is correct
31 Correct 1817 ms 1038736 KB Output is correct
32 Correct 1775 ms 1038912 KB Output is correct
33 Correct 743 ms 1038568 KB Output is correct
34 Correct 784 ms 1038456 KB Output is correct
35 Correct 1577 ms 1038584 KB Output is correct
36 Correct 1299 ms 1038684 KB Output is correct
37 Correct 788 ms 1038360 KB Output is correct
38 Correct 788 ms 1038688 KB Output is correct
39 Correct 930 ms 1038472 KB Output is correct
40 Correct 743 ms 1038600 KB Output is correct
41 Correct 761 ms 1038584 KB Output is correct
42 Correct 873 ms 1038584 KB Output is correct
43 Correct 733 ms 1038476 KB Output is correct
44 Correct 676 ms 1038456 KB Output is correct
45 Correct 667 ms 1038328 KB Output is correct
46 Correct 1113 ms 1044752 KB Output is correct
47 Execution timed out 18090 ms 1046632 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 1032628 KB Output is correct
2 Correct 591 ms 1032724 KB Output is correct
3 Correct 512 ms 1032656 KB Output is correct
4 Correct 588 ms 1032648 KB Output is correct
5 Correct 548 ms 1032696 KB Output is correct
6 Correct 587 ms 1032608 KB Output is correct
7 Correct 643 ms 1032700 KB Output is correct
8 Correct 568 ms 1032696 KB Output is correct
9 Correct 641 ms 1032656 KB Output is correct
10 Correct 637 ms 1032568 KB Output is correct
11 Correct 541 ms 1032592 KB Output is correct
12 Correct 561 ms 1032640 KB Output is correct
13 Correct 570 ms 1032688 KB Output is correct
14 Correct 629 ms 1032632 KB Output is correct
15 Correct 554 ms 1032640 KB Output is correct
16 Correct 558 ms 1032700 KB Output is correct
17 Correct 650 ms 1032696 KB Output is correct
18 Correct 609 ms 1032700 KB Output is correct
19 Correct 542 ms 1032696 KB Output is correct
20 Correct 584 ms 1032952 KB Output is correct
21 Correct 580 ms 1032696 KB Output is correct
22 Correct 539 ms 1032696 KB Output is correct
23 Correct 572 ms 1032696 KB Output is correct
24 Correct 587 ms 1032776 KB Output is correct
25 Correct 532 ms 1032696 KB Output is correct
26 Correct 557 ms 1033124 KB Output is correct
27 Correct 600 ms 1034360 KB Output is correct
28 Correct 573 ms 1034464 KB Output is correct
29 Correct 951 ms 1038584 KB Output is correct
30 Correct 1088 ms 1038712 KB Output is correct
31 Correct 1817 ms 1038736 KB Output is correct
32 Correct 1775 ms 1038912 KB Output is correct
33 Correct 743 ms 1038568 KB Output is correct
34 Correct 784 ms 1038456 KB Output is correct
35 Correct 1577 ms 1038584 KB Output is correct
36 Correct 1299 ms 1038684 KB Output is correct
37 Correct 788 ms 1038360 KB Output is correct
38 Correct 788 ms 1038688 KB Output is correct
39 Correct 930 ms 1038472 KB Output is correct
40 Correct 743 ms 1038600 KB Output is correct
41 Correct 761 ms 1038584 KB Output is correct
42 Correct 873 ms 1038584 KB Output is correct
43 Correct 733 ms 1038476 KB Output is correct
44 Correct 676 ms 1038456 KB Output is correct
45 Correct 667 ms 1038328 KB Output is correct
46 Correct 1113 ms 1044752 KB Output is correct
47 Execution timed out 18090 ms 1046632 KB Time limit exceeded
48 Halted 0 ms 0 KB -