oj.uz

Submission #291498

# Submission time Handle Problem Language Result Execution time Memory
291498 2020-09-05T12:11:00 Z TadijaSebez Wild Boar (JOI18_wild_boar) C++11
12 / 100
 750 ms 266872 KB 
#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=4;
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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 264568 KB Output is correct
2 Correct 143 ms 264696 KB Output is correct
3 Correct 143 ms 264696 KB Output is correct
4 Correct 146 ms 264696 KB Output is correct
5 Correct 145 ms 264696 KB Output is correct
6 Correct 144 ms 264696 KB Output is correct
7 Correct 143 ms 264696 KB Output is correct
8 Correct 145 ms 264696 KB Output is correct
9 Correct 158 ms 264568 KB Output is correct
10 Correct 150 ms 264568 KB Output is correct
11 Correct 150 ms 264568 KB Output is correct
12 Correct 148 ms 264568 KB Output is correct
13 Correct 146 ms 264568 KB Output is correct
14 Correct 154 ms 264676 KB Output is correct
15 Correct 145 ms 264696 KB Output is correct
16 Correct 147 ms 264568 KB Output is correct
17 Correct 147 ms 264700 KB Output is correct
18 Correct 154 ms 264696 KB Output is correct
19 Correct 146 ms 264696 KB Output is correct
20 Correct 146 ms 264696 KB Output is correct
21 Correct 148 ms 264696 KB Output is correct
22 Correct 165 ms 264588 KB Output is correct
23 Correct 145 ms 264696 KB Output is correct
24 Correct 146 ms 264696 KB Output is correct
25 Correct 163 ms 264696 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 264568 KB Output is correct
2 Correct 143 ms 264696 KB Output is correct
3 Correct 143 ms 264696 KB Output is correct
4 Correct 146 ms 264696 KB Output is correct
5 Correct 145 ms 264696 KB Output is correct
6 Correct 144 ms 264696 KB Output is correct
7 Correct 143 ms 264696 KB Output is correct
8 Correct 145 ms 264696 KB Output is correct
9 Correct 158 ms 264568 KB Output is correct
10 Correct 150 ms 264568 KB Output is correct
11 Correct 150 ms 264568 KB Output is correct
12 Correct 148 ms 264568 KB Output is correct
13 Correct 146 ms 264568 KB Output is correct
14 Correct 154 ms 264676 KB Output is correct
15 Correct 145 ms 264696 KB Output is correct
16 Correct 147 ms 264568 KB Output is correct
17 Correct 147 ms 264700 KB Output is correct
18 Correct 154 ms 264696 KB Output is correct
19 Correct 146 ms 264696 KB Output is correct
20 Correct 146 ms 264696 KB Output is correct
21 Correct 148 ms 264696 KB Output is correct
22 Correct 165 ms 264588 KB Output is correct
23 Correct 145 ms 264696 KB Output is correct
24 Correct 146 ms 264696 KB Output is correct
25 Correct 163 ms 264696 KB Output is correct
26 Correct 153 ms 264696 KB Output is correct
27 Correct 439 ms 266744 KB Output is correct
28 Correct 422 ms 266744 KB Output is correct
29 Incorrect 750 ms 266872 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 264568 KB Output is correct
2 Correct 143 ms 264696 KB Output is correct
3 Correct 143 ms 264696 KB Output is correct
4 Correct 146 ms 264696 KB Output is correct
5 Correct 145 ms 264696 KB Output is correct
6 Correct 144 ms 264696 KB Output is correct
7 Correct 143 ms 264696 KB Output is correct
8 Correct 145 ms 264696 KB Output is correct
9 Correct 158 ms 264568 KB Output is correct
10 Correct 150 ms 264568 KB Output is correct
11 Correct 150 ms 264568 KB Output is correct
12 Correct 148 ms 264568 KB Output is correct
13 Correct 146 ms 264568 KB Output is correct
14 Correct 154 ms 264676 KB Output is correct
15 Correct 145 ms 264696 KB Output is correct
16 Correct 147 ms 264568 KB Output is correct
17 Correct 147 ms 264700 KB Output is correct
18 Correct 154 ms 264696 KB Output is correct
19 Correct 146 ms 264696 KB Output is correct
20 Correct 146 ms 264696 KB Output is correct
21 Correct 148 ms 264696 KB Output is correct
22 Correct 165 ms 264588 KB Output is correct
23 Correct 145 ms 264696 KB Output is correct
24 Correct 146 ms 264696 KB Output is correct
25 Correct 163 ms 264696 KB Output is correct
26 Correct 153 ms 264696 KB Output is correct
27 Correct 439 ms 266744 KB Output is correct
28 Correct 422 ms 266744 KB Output is correct
29 Incorrect 750 ms 266872 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 264568 KB Output is correct
2 Correct 143 ms 264696 KB Output is correct
3 Correct 143 ms 264696 KB Output is correct
4 Correct 146 ms 264696 KB Output is correct
5 Correct 145 ms 264696 KB Output is correct
6 Correct 144 ms 264696 KB Output is correct
7 Correct 143 ms 264696 KB Output is correct
8 Correct 145 ms 264696 KB Output is correct
9 Correct 158 ms 264568 KB Output is correct
10 Correct 150 ms 264568 KB Output is correct
11 Correct 150 ms 264568 KB Output is correct
12 Correct 148 ms 264568 KB Output is correct
13 Correct 146 ms 264568 KB Output is correct
14 Correct 154 ms 264676 KB Output is correct
15 Correct 145 ms 264696 KB Output is correct
16 Correct 147 ms 264568 KB Output is correct
17 Correct 147 ms 264700 KB Output is correct
18 Correct 154 ms 264696 KB Output is correct
19 Correct 146 ms 264696 KB Output is correct
20 Correct 146 ms 264696 KB Output is correct
21 Correct 148 ms 264696 KB Output is correct
22 Correct 165 ms 264588 KB Output is correct
23 Correct 145 ms 264696 KB Output is correct
24 Correct 146 ms 264696 KB Output is correct
25 Correct 163 ms 264696 KB Output is correct
26 Correct 153 ms 264696 KB Output is correct
27 Correct 439 ms 266744 KB Output is correct
28 Correct 422 ms 266744 KB Output is correct
29 Incorrect 750 ms 266872 KB Output isn't correct
30 Halted 0 ms 0 KB -