oj.uz

Submission #47631

# Submission time Handle Problem Language Result Execution time Memory
47631 2018-05-06T05:44:26 Z zscoder Wild Boar (JOI18_wild_boar) C++17
100 / 100
 9209 ms 810792 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
 
vector<pair<int,int> > edges;
ll dist[4111][4111];
int n,m,q,L; 
vector<pair<ii,int> > adj[2111];
vi in[2111];
vi out[2111];
ll orid[2001][2001];
int getid(int a, int b)
{
	return (a*2+b);
}
const ll INF=ll(1e18);
int a[211111];
ll D[2111][2111][5];
vector<pair<int,int> > paths[2111][2111];
vector<ll> W;
 
const int DIM = 5;
struct state
{
	ll a[DIM][DIM];
	ll *operator [] (int r) { return a[r]; };
	state(ll x = 0)
	{
		memset(a, 0, sizeof a);
		if(x)
		{
			for(int i = 0; i < DIM; i++)
			{
				for(int j=0;j < DIM;j++)
				{
					if(i==j) a[i][j]=0;
					else a[i][j] = x;
				}
			}
		}
	}
};

state operator + (state A, state B) 
{
	state C;
	for(int i=0;i<DIM;i++)
	{
		for(int j=0;j<DIM;j++)
		{
			C[i][j] = INF;
		}
		for(int j=0;j<DIM;j++)
		{
			for(int k=0;k<DIM;k++)
			{
				C[i][k] = min(C[i][k], A[j][k] + B[i][j]);
			}
		}
	}
	return C;
}

state st[263000];

void build(int n) 
{ 
	for(int i = n - 1; i > 0; --i) 
	{
		st[i] = st[i<<1] + st[i<<1|1];
	}
}

void modify(int n, int p, state value) 
{
	for(st[p += n] = value; p >>= 1; ) 
	{
		st[p] = st[p<<1] + st[p<<1|1];
	}
}

state construct(int i)
{
	state cur;
	for(int j=0;j<DIM;j++){for(int k=0;k<DIM;k++){cur[j][k]=INF;}}
	for(int j=0;j<DIM;j++)
	{
		for(int k=0;k<DIM;k++)
		{
			if(paths[a[i-1]][a[i]][j].se!=-1&&paths[a[i]][a[i+1]][k].fi!=-1&&paths[a[i-1]][a[i]][j].se!=paths[a[i]][a[i+1]][k].fi)
			{
				cur[k][j] = min(cur[k][j], D[a[i]][a[i+1]][k]);
			}
		}
	}
	return cur;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i=0;i<263000;i++) st[i] = state(INF);
	cin>>n>>m>>q>>L;
	for(int i=0;i<m;i++)
	{
		int u,v,w; cin>>u>>v>>w; u--; v--; edges.pb({u,v}); W.pb(w); edges.pb({v,u}); W.pb(w); orid[u][v]=orid[v][u]=w;
		adj[u].pb(mp(mp(v,w),i*2)); adj[v].pb(mp(mp(u,w),i*2+1));
		out[u].pb(i*2); out[v].pb(i*2+1);
		in[u].pb(i*2+1); in[v].pb(i*2);
	}
	m*=2;
	for(int i=0;i<m;i++)
	{
		priority_queue<ii,vector<ii>,greater<ii> > pq;
		int s = i;
		pq.push(mp(0,s));
		for(int k=0;k<m;k++) dist[s][k] = INF;
		dist[s][s] = 0;
		while(!pq.empty())
		{
			ll d=pq.top().fi; int u = pq.top().se; pq.pop();
			int vertex = edges[u].se; int edgeno = u;
			for(auto k:adj[vertex])
			{
				int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
				if(id/2==edgeno/2) continue;
				int u1 = edges[id].fi; int v1 = edges[id].se;
				assert(u1==vertex);
				if(dist[s][id]>d)
				{
					dist[s][id] = d;
					pq.push(mp(d+w, id));
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(i==j) continue;
			ll mn=INF; ii cur=mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][0] = mn;
			paths[i][j].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(edges[k].se!=paths[i][j][0].fi&&dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn&&j!=paths[i][j][0].fi)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][1] = mn;
			paths[i][j].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(edges[k].se!=paths[i][j][0].fi&&edges[l].fi!=paths[i][j][1].se&&dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn&&j!=paths[i][j][0].fi&&i!=paths[i][j][1].se)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][2] = mn;
			paths[i][j].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(edges[l].fi!=paths[i][j][0].se&&dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn&&i!=paths[i][j][0].se)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][3] = mn;
			paths[i][j].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(edges[k].se!=paths[i][j][3].fi&&edges[l].fi!=paths[i][j][0].se&&dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn&&j!=paths[i][j][3].fi&&i!=paths[i][j][0].se)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][4] = mn;
			paths[i][j].pb(cur);
		}
	}
	for(int i=0;i<L;i++)
	{
		cin>>a[i]; a[i]--;
	}
	ll BIGL = 1;
	while(BIGL<L-2) BIGL*=2;
	for(int i=1;i+1<L;i++)
	{
		st[BIGL+i-1] = construct(i);
	}
	build(BIGL);
	for(int zz=0;zz<q;zz++)
	{
		int y,z; cin>>y>>z; y--; z--; a[y]=z;
		if(y>=1&&y+1<L)
		{
			modify(BIGL, y-1, construct(y));
		}
		if(y>=2&&y<L)
		{
			modify(BIGL, y-2, construct(y-1));
		}
		if(y+2<L)
		{
			modify(BIGL, y, construct(y+1));
		}
		vector<ll> dp;
		for(int i=0;i<5;i++) dp.pb(D[a[0]][a[1]][i]);
		ll ans = INF;
		for(int i=0;i<5;i++)
		{
			for(int j=0;j<5;j++)
			{
				ans = min(ans, dp[j] + st[1][i][j]);
			}
		}
		if(ans>=INF) ans=-1;
		cout<<ans<<'\n';
	}
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:143:9: warning: unused variable 'v' [-Wunused-variable]
     int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
         ^
wild_boar.cpp:145:32: warning: unused variable 'v1' [-Wunused-variable]
     int u1 = edges[id].fi; int v1 = edges[id].se;
                                ^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 156664 KB Output is correct
2 Correct 150 ms 156812 KB Output is correct
3 Correct 149 ms 156832 KB Output is correct
4 Correct 146 ms 156956 KB Output is correct
5 Correct 150 ms 157124 KB Output is correct
6 Correct 147 ms 157124 KB Output is correct
7 Correct 147 ms 157124 KB Output is correct
8 Correct 147 ms 157124 KB Output is correct
9 Correct 154 ms 157124 KB Output is correct
10 Correct 149 ms 157124 KB Output is correct
11 Correct 149 ms 157124 KB Output is correct
12 Correct 148 ms 157124 KB Output is correct
13 Correct 148 ms 157124 KB Output is correct
14 Correct 150 ms 157124 KB Output is correct
15 Correct 149 ms 157124 KB Output is correct
16 Correct 152 ms 157124 KB Output is correct
17 Correct 147 ms 157124 KB Output is correct
18 Correct 152 ms 157192 KB Output is correct
19 Correct 146 ms 157192 KB Output is correct
20 Correct 161 ms 157192 KB Output is correct
21 Correct 147 ms 157192 KB Output is correct
22 Correct 151 ms 157192 KB Output is correct
23 Correct 152 ms 157192 KB Output is correct
24 Correct 149 ms 157216 KB Output is correct
25 Correct 149 ms 157348 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 156664 KB Output is correct
2 Correct 150 ms 156812 KB Output is correct
3 Correct 149 ms 156832 KB Output is correct
4 Correct 146 ms 156956 KB Output is correct
5 Correct 150 ms 157124 KB Output is correct
6 Correct 147 ms 157124 KB Output is correct
7 Correct 147 ms 157124 KB Output is correct
8 Correct 147 ms 157124 KB Output is correct
9 Correct 154 ms 157124 KB Output is correct
10 Correct 149 ms 157124 KB Output is correct
11 Correct 149 ms 157124 KB Output is correct
12 Correct 148 ms 157124 KB Output is correct
13 Correct 148 ms 157124 KB Output is correct
14 Correct 150 ms 157124 KB Output is correct
15 Correct 149 ms 157124 KB Output is correct
16 Correct 152 ms 157124 KB Output is correct
17 Correct 147 ms 157124 KB Output is correct
18 Correct 152 ms 157192 KB Output is correct
19 Correct 146 ms 157192 KB Output is correct
20 Correct 161 ms 157192 KB Output is correct
21 Correct 147 ms 157192 KB Output is correct
22 Correct 151 ms 157192 KB Output is correct
23 Correct 152 ms 157192 KB Output is correct
24 Correct 149 ms 157216 KB Output is correct
25 Correct 149 ms 157348 KB Output is correct
26 Correct 148 ms 157624 KB Output is correct
27 Correct 219 ms 160920 KB Output is correct
28 Correct 216 ms 161132 KB Output is correct
29 Correct 297 ms 165644 KB Output is correct
30 Correct 285 ms 165936 KB Output is correct
31 Correct 285 ms 166164 KB Output is correct
32 Correct 288 ms 166368 KB Output is correct
33 Correct 295 ms 168568 KB Output is correct
34 Correct 300 ms 169028 KB Output is correct
35 Correct 285 ms 169156 KB Output is correct
36 Correct 280 ms 169400 KB Output is correct
37 Correct 300 ms 169596 KB Output is correct
38 Correct 306 ms 172460 KB Output is correct
39 Correct 269 ms 172692 KB Output is correct
40 Correct 306 ms 172972 KB Output is correct
41 Correct 304 ms 173500 KB Output is correct
42 Correct 277 ms 175360 KB Output is correct
43 Correct 289 ms 177100 KB Output is correct
44 Correct 286 ms 177524 KB Output is correct
45 Correct 284 ms 181520 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 156664 KB Output is correct
2 Correct 150 ms 156812 KB Output is correct
3 Correct 149 ms 156832 KB Output is correct
4 Correct 146 ms 156956 KB Output is correct
5 Correct 150 ms 157124 KB Output is correct
6 Correct 147 ms 157124 KB Output is correct
7 Correct 147 ms 157124 KB Output is correct
8 Correct 147 ms 157124 KB Output is correct
9 Correct 154 ms 157124 KB Output is correct
10 Correct 149 ms 157124 KB Output is correct
11 Correct 149 ms 157124 KB Output is correct
12 Correct 148 ms 157124 KB Output is correct
13 Correct 148 ms 157124 KB Output is correct
14 Correct 150 ms 157124 KB Output is correct
15 Correct 149 ms 157124 KB Output is correct
16 Correct 152 ms 157124 KB Output is correct
17 Correct 147 ms 157124 KB Output is correct
18 Correct 152 ms 157192 KB Output is correct
19 Correct 146 ms 157192 KB Output is correct
20 Correct 161 ms 157192 KB Output is correct
21 Correct 147 ms 157192 KB Output is correct
22 Correct 151 ms 157192 KB Output is correct
23 Correct 152 ms 157192 KB Output is correct
24 Correct 149 ms 157216 KB Output is correct
25 Correct 149 ms 157348 KB Output is correct
26 Correct 148 ms 157624 KB Output is correct
27 Correct 219 ms 160920 KB Output is correct
28 Correct 216 ms 161132 KB Output is correct
29 Correct 297 ms 165644 KB Output is correct
30 Correct 285 ms 165936 KB Output is correct
31 Correct 285 ms 166164 KB Output is correct
32 Correct 288 ms 166368 KB Output is correct
33 Correct 295 ms 168568 KB Output is correct
34 Correct 300 ms 169028 KB Output is correct
35 Correct 285 ms 169156 KB Output is correct
36 Correct 280 ms 169400 KB Output is correct
37 Correct 300 ms 169596 KB Output is correct
38 Correct 306 ms 172460 KB Output is correct
39 Correct 269 ms 172692 KB Output is correct
40 Correct 306 ms 172972 KB Output is correct
41 Correct 304 ms 173500 KB Output is correct
42 Correct 277 ms 175360 KB Output is correct
43 Correct 289 ms 177100 KB Output is correct
44 Correct 286 ms 177524 KB Output is correct
45 Correct 284 ms 181520 KB Output is correct
46 Correct 369 ms 181520 KB Output is correct
47 Correct 7138 ms 326776 KB Output is correct
48 Correct 6194 ms 376640 KB Output is correct
49 Correct 5174 ms 422016 KB Output is correct
50 Correct 5546 ms 422300 KB Output is correct
51 Correct 6131 ms 422468 KB Output is correct
52 Correct 4035 ms 423376 KB Output is correct
53 Correct 4043 ms 423712 KB Output is correct
54 Correct 4344 ms 424404 KB Output is correct
55 Correct 4304 ms 424596 KB Output is correct
56 Correct 4227 ms 450956 KB Output is correct
57 Correct 4356 ms 479772 KB Output is correct
58 Correct 4362 ms 510168 KB Output is correct
59 Correct 4335 ms 543440 KB Output is correct
60 Correct 4291 ms 578700 KB Output is correct
61 Correct 4291 ms 616608 KB Output is correct
62 Correct 3923 ms 656548 KB Output is correct
63 Correct 3964 ms 698608 KB Output is correct
64 Correct 2537 ms 788660 KB Output is correct
65 Correct 2382 ms 789196 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 156664 KB Output is correct
2 Correct 150 ms 156812 KB Output is correct
3 Correct 149 ms 156832 KB Output is correct
4 Correct 146 ms 156956 KB Output is correct
5 Correct 150 ms 157124 KB Output is correct
6 Correct 147 ms 157124 KB Output is correct
7 Correct 147 ms 157124 KB Output is correct
8 Correct 147 ms 157124 KB Output is correct
9 Correct 154 ms 157124 KB Output is correct
10 Correct 149 ms 157124 KB Output is correct
11 Correct 149 ms 157124 KB Output is correct
12 Correct 148 ms 157124 KB Output is correct
13 Correct 148 ms 157124 KB Output is correct
14 Correct 150 ms 157124 KB Output is correct
15 Correct 149 ms 157124 KB Output is correct
16 Correct 152 ms 157124 KB Output is correct
17 Correct 147 ms 157124 KB Output is correct
18 Correct 152 ms 157192 KB Output is correct
19 Correct 146 ms 157192 KB Output is correct
20 Correct 161 ms 157192 KB Output is correct
21 Correct 147 ms 157192 KB Output is correct
22 Correct 151 ms 157192 KB Output is correct
23 Correct 152 ms 157192 KB Output is correct
24 Correct 149 ms 157216 KB Output is correct
25 Correct 149 ms 157348 KB Output is correct
26 Correct 148 ms 157624 KB Output is correct
27 Correct 219 ms 160920 KB Output is correct
28 Correct 216 ms 161132 KB Output is correct
29 Correct 297 ms 165644 KB Output is correct
30 Correct 285 ms 165936 KB Output is correct
31 Correct 285 ms 166164 KB Output is correct
32 Correct 288 ms 166368 KB Output is correct
33 Correct 295 ms 168568 KB Output is correct
34 Correct 300 ms 169028 KB Output is correct
35 Correct 285 ms 169156 KB Output is correct
36 Correct 280 ms 169400 KB Output is correct
37 Correct 300 ms 169596 KB Output is correct
38 Correct 306 ms 172460 KB Output is correct
39 Correct 269 ms 172692 KB Output is correct
40 Correct 306 ms 172972 KB Output is correct
41 Correct 304 ms 173500 KB Output is correct
42 Correct 277 ms 175360 KB Output is correct
43 Correct 289 ms 177100 KB Output is correct
44 Correct 286 ms 177524 KB Output is correct
45 Correct 284 ms 181520 KB Output is correct
46 Correct 369 ms 181520 KB Output is correct
47 Correct 7138 ms 326776 KB Output is correct
48 Correct 6194 ms 376640 KB Output is correct
49 Correct 5174 ms 422016 KB Output is correct
50 Correct 5546 ms 422300 KB Output is correct
51 Correct 6131 ms 422468 KB Output is correct
52 Correct 4035 ms 423376 KB Output is correct
53 Correct 4043 ms 423712 KB Output is correct
54 Correct 4344 ms 424404 KB Output is correct
55 Correct 4304 ms 424596 KB Output is correct
56 Correct 4227 ms 450956 KB Output is correct
57 Correct 4356 ms 479772 KB Output is correct
58 Correct 4362 ms 510168 KB Output is correct
59 Correct 4335 ms 543440 KB Output is correct
60 Correct 4291 ms 578700 KB Output is correct
61 Correct 4291 ms 616608 KB Output is correct
62 Correct 3923 ms 656548 KB Output is correct
63 Correct 3964 ms 698608 KB Output is correct
64 Correct 2537 ms 788660 KB Output is correct
65 Correct 2382 ms 789196 KB Output is correct
66 Correct 216 ms 789196 KB Output is correct
67 Correct 1303 ms 789196 KB Output is correct
68 Correct 2447 ms 789196 KB Output is correct
69 Correct 3021 ms 790208 KB Output is correct
70 Correct 4332 ms 792016 KB Output is correct
71 Correct 8880 ms 792016 KB Output is correct
72 Correct 8138 ms 792016 KB Output is correct
73 Correct 6142 ms 792016 KB Output is correct
74 Correct 6059 ms 792016 KB Output is correct
75 Correct 6052 ms 792016 KB Output is correct
76 Correct 6909 ms 792016 KB Output is correct
77 Correct 8037 ms 792016 KB Output is correct
78 Correct 9209 ms 792016 KB Output is correct
79 Correct 6067 ms 792016 KB Output is correct
80 Correct 6120 ms 792016 KB Output is correct
81 Correct 6411 ms 792016 KB Output is correct
82 Correct 6017 ms 792016 KB Output is correct
83 Correct 5827 ms 792016 KB Output is correct
84 Correct 5716 ms 792016 KB Output is correct
85 Correct 4544 ms 810792 KB Output is correct