Submission #291497

#	Time	Username	Problem	Language	Result	Execution time	Memory
291497		TadijaSebez	Wild Boar (JOI18_wild_boar)	C++11	100 / 100	8440 ms	336304 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define ll long long
const int N=2005;
const int M=200050;
const int C=5;
const ll inf=4e18;
struct path{
	int u,v;ll cost;
	path(int a=0,int b=0,ll c=inf):u(a),v(b),cost(c){}
};
bool operator < (path a,path b){return a.cost>b.cost;}
path dist[N][N][C];
bool push(path tmp[C],path now,int o=C){
	int i,c1=0,c2=0;
	for(i=0;i<o&&tmp[i].cost!=inf;i++){
		if(tmp[i].u==now.u&&tmp[i].v==now.v)return 0;
		c1+=tmp[i].u==now.u;
		c2+=tmp[i].v==now.v;
	}
	if(c1>1||c2>1||i==C)return 0;
	if(tmp[i]<now)tmp[i]=now;
	return 1;
}
vector<pii> E[N];
int ls[M],rs[M],tsz,root;
path node[M][C];
void pull(int c){
	for(int i=0;i<C;i++){
		node[c][i]=path();
		for(int j=0;j<C;j++)
			for(int k=0;k<C;k++)
				if(node[ls[c]][j].v!=node[rs[c]][k].u)
					push(node[c],path(node[ls[c]][j].u,node[rs[c]][k].v,node[ls[c]][j].cost+node[rs[c]][k].cost),i);
	}
}
int x[M];
void Set(int&c,int ss,int se,int qi){
	if(!c)c=++tsz;
	if(ss==se){
		for(int i=0;i<C;i++)node[c][i]=dist[x[ss]][x[ss+1]][i];
		return;
	}
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ss,mid,qi);
	else Set(rs[c],mid+1,se,qi);
	pull(c);
}
int main(){
	int n,m,t,l;
	scanf("%i %i %i %i",&n,&m,&t,&l);
	for(int i=1,u,v,w;i<=m;i++)scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
	for(int u=1;u<=n;u++){
		priority_queue<pair<path,int>> pq;
		for(auto e:E[u])pq.push({path(e.first,u,e.second),e.first});
		while(pq.size()){
			pair<path,int> now=pq.top();
			pq.pop();
			if(!push(dist[u][now.second],now.first))continue;
			for(auto e:E[now.second])if(e.first!=now.first.v)
				pq.push({path(now.first.u,now.second,now.first.cost+e.second),e.first});
		}
	}
	for(int i=1;i<=l;i++)scanf("%i",&x[i]);
	for(int i=1;i<l;i++)Set(root,1,l-1,i);
	while(t--){
		int i,y;
		scanf("%i %i",&i,&y);
		x[i]=y;
		if(i!=1)Set(root,1,l-1,i-1);
		if(i!=l)Set(root,1,l-1,i);
		ll ans=node[root][0].cost;
		printf("%lld\n",ans<inf?ans:-1);
	}
	return 0;
}

Compilation message (stderr)

wild_boar.cpp: In function 'void Set(int&, int, int, int)':
wild_boar.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int mid=ss+se>>1;
      |          ~~^~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%i %i %i %i",&n,&m,&t,&l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:54:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  for(int i=1,u,v,w;i<=m;i++)scanf("%i %i %i",&u,&v,&w),E[u].pb({v,w}),E[v].pb({u,w});
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:66:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  for(int i=1;i<=l;i++)scanf("%i",&x[i]);
      |                       ~~~~~^~~~~~~~~~~~
wild_boar.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf("%i %i",&i,&y);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38