Submission #243917

#	Time	Username	Problem	Language	Result	Execution time	Memory
243917		arnold518	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	6972 ms	412580 KiB

wild_boar

#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/2+10][MAXN/2+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}); dist[i][i]=E[i].w;
		while(!PQ.empty())
		{
			Queue now=PQ.top(); PQ.pop();
			if(dist[i][now.v]!=now.w) continue;
			for(auto nxt : adj[E[now.v].v]) if(nxt.v!=E[now.v].u && dist[i][nxt.p]>now.w+nxt.w)
			{
				dist[i][nxt.p]=now.w+nxt.w;
				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 (stderr)

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:124: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:125: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:126: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:127: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:135: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:141: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 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38