oj.uz

Submission #46962

# Submission time Handle Problem Language Result Execution time Memory
46962 2018-04-25T12:56:59 Z zscoder Wild Boar (JOI18_wild_boar) C++17
12 / 100
 309 ms 164076 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[260000];

void printstate(state cur)
{
	for(int j=0;j<DIM;j++)
	{
		for(int k=0;k<DIM;k++)
		{
			cerr<<cur[j][k]<<' ';
		}
		cerr<<'\n';
	}
	cerr<<'\n';
}

void build(int n) 
{ 
	for(int i = n - 1; i > 0; --i) 
	{
		//cerr<<"COMBINE : "<<(i<<1)<<' '<<((i<<1|1))<<'\n';
		//printstate(st[i<<1]); printstate(st[i<<1|1]);
		st[i] = st[i<<1] + st[i<<1|1];
		//printstate(st[i]);
	}
}

void modify(int n, int p, state value) 
{
	//printstate(value);
	for (st[p += n] = value; p >>= 1; ) 
	{
		//cerr<<"COMBINE : "<<(p<<1)<<' '<<(p<<1|1)<<'\n';
		//printstate(st[p<<1]); printstate(st[p<<1|1]);
		st[p] = st[p<<1] + st[p<<1|1];
		//printstate(st[p]);
	}
}

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++)
		{
			//cerr<<"ALERT : "<<i<<' '<<j<<' '<<k<<' '<<paths[a[i-1]][a[i]][j].se<<' '<<paths[a[i]][a[i+1]][k].fi<<' '<<D[a[i]][a[i+1]][k]<<'\n';
			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]);
			}
		}
	}
	//printstate(cur);
	return cur;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i=0;i<260000;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);
	//printstate(st[1]);
	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]);
		//cerr<<"DP : ";
		//for(int i=0;i<5;i++) cerr<<dp[i]<<' ';
		//cerr<<'\n';
		//printstate(st[1]);
		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 : ";
		cout<<ans<<'\n';
		/*
			int pre = i&1; int cur = pre^1;
			for(int j=0;j<5;j++)
			{
				dp[cur][j]=INF;
			}
			for(int j=0;j<5;j++)
			{
				if(dp[pre][j]<INF)
				{
					ll v=dp[pre][j];
					for(int k=0;k<5;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)
						{
							dp[cur][k] = min(dp[cur][k], v + D[a[i]][a[i+1]][k]);
						}
					}
				}
			}
		}
		ll mn = INF;
		for(int i=0;i<5;i++) mn=min(mn,dp[(L+1)&1][i]);
		if(mn>=INF) mn=-1;
		cout<<mn<<'\n';
		*/
		
	}
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:165:9: warning: unused variable 'v' [-Wunused-variable]
     int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
         ^
wild_boar.cpp:167: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 164 ms 156156 KB Output is correct
2 Correct 153 ms 156244 KB Output is correct
3 Correct 174 ms 156336 KB Output is correct
4 Correct 157 ms 156336 KB Output is correct
5 Correct 161 ms 156412 KB Output is correct
6 Correct 170 ms 156488 KB Output is correct
7 Correct 156 ms 156488 KB Output is correct
8 Correct 148 ms 156488 KB Output is correct
9 Correct 155 ms 156488 KB Output is correct
10 Correct 155 ms 156520 KB Output is correct
11 Correct 158 ms 156584 KB Output is correct
12 Correct 179 ms 156584 KB Output is correct
13 Correct 159 ms 156584 KB Output is correct
14 Correct 160 ms 156584 KB Output is correct
15 Correct 161 ms 156584 KB Output is correct
16 Correct 159 ms 156584 KB Output is correct
17 Correct 176 ms 156584 KB Output is correct
18 Correct 156 ms 156584 KB Output is correct
19 Correct 168 ms 156584 KB Output is correct
20 Correct 156 ms 156584 KB Output is correct
21 Correct 153 ms 156584 KB Output is correct
22 Correct 155 ms 156584 KB Output is correct
23 Correct 152 ms 156584 KB Output is correct
24 Correct 151 ms 156584 KB Output is correct
25 Correct 159 ms 156584 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 156156 KB Output is correct
2 Correct 153 ms 156244 KB Output is correct
3 Correct 174 ms 156336 KB Output is correct
4 Correct 157 ms 156336 KB Output is correct
5 Correct 161 ms 156412 KB Output is correct
6 Correct 170 ms 156488 KB Output is correct
7 Correct 156 ms 156488 KB Output is correct
8 Correct 148 ms 156488 KB Output is correct
9 Correct 155 ms 156488 KB Output is correct
10 Correct 155 ms 156520 KB Output is correct
11 Correct 158 ms 156584 KB Output is correct
12 Correct 179 ms 156584 KB Output is correct
13 Correct 159 ms 156584 KB Output is correct
14 Correct 160 ms 156584 KB Output is correct
15 Correct 161 ms 156584 KB Output is correct
16 Correct 159 ms 156584 KB Output is correct
17 Correct 176 ms 156584 KB Output is correct
18 Correct 156 ms 156584 KB Output is correct
19 Correct 168 ms 156584 KB Output is correct
20 Correct 156 ms 156584 KB Output is correct
21 Correct 153 ms 156584 KB Output is correct
22 Correct 155 ms 156584 KB Output is correct
23 Correct 152 ms 156584 KB Output is correct
24 Correct 151 ms 156584 KB Output is correct
25 Correct 159 ms 156584 KB Output is correct
26 Correct 162 ms 156964 KB Output is correct
27 Correct 225 ms 159832 KB Output is correct
28 Correct 204 ms 159832 KB Output is correct
29 Incorrect 309 ms 164076 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 156156 KB Output is correct
2 Correct 153 ms 156244 KB Output is correct
3 Correct 174 ms 156336 KB Output is correct
4 Correct 157 ms 156336 KB Output is correct
5 Correct 161 ms 156412 KB Output is correct
6 Correct 170 ms 156488 KB Output is correct
7 Correct 156 ms 156488 KB Output is correct
8 Correct 148 ms 156488 KB Output is correct
9 Correct 155 ms 156488 KB Output is correct
10 Correct 155 ms 156520 KB Output is correct
11 Correct 158 ms 156584 KB Output is correct
12 Correct 179 ms 156584 KB Output is correct
13 Correct 159 ms 156584 KB Output is correct
14 Correct 160 ms 156584 KB Output is correct
15 Correct 161 ms 156584 KB Output is correct
16 Correct 159 ms 156584 KB Output is correct
17 Correct 176 ms 156584 KB Output is correct
18 Correct 156 ms 156584 KB Output is correct
19 Correct 168 ms 156584 KB Output is correct
20 Correct 156 ms 156584 KB Output is correct
21 Correct 153 ms 156584 KB Output is correct
22 Correct 155 ms 156584 KB Output is correct
23 Correct 152 ms 156584 KB Output is correct
24 Correct 151 ms 156584 KB Output is correct
25 Correct 159 ms 156584 KB Output is correct
26 Correct 162 ms 156964 KB Output is correct
27 Correct 225 ms 159832 KB Output is correct
28 Correct 204 ms 159832 KB Output is correct
29 Incorrect 309 ms 164076 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 156156 KB Output is correct
2 Correct 153 ms 156244 KB Output is correct
3 Correct 174 ms 156336 KB Output is correct
4 Correct 157 ms 156336 KB Output is correct
5 Correct 161 ms 156412 KB Output is correct
6 Correct 170 ms 156488 KB Output is correct
7 Correct 156 ms 156488 KB Output is correct
8 Correct 148 ms 156488 KB Output is correct
9 Correct 155 ms 156488 KB Output is correct
10 Correct 155 ms 156520 KB Output is correct
11 Correct 158 ms 156584 KB Output is correct
12 Correct 179 ms 156584 KB Output is correct
13 Correct 159 ms 156584 KB Output is correct
14 Correct 160 ms 156584 KB Output is correct
15 Correct 161 ms 156584 KB Output is correct
16 Correct 159 ms 156584 KB Output is correct
17 Correct 176 ms 156584 KB Output is correct
18 Correct 156 ms 156584 KB Output is correct
19 Correct 168 ms 156584 KB Output is correct
20 Correct 156 ms 156584 KB Output is correct
21 Correct 153 ms 156584 KB Output is correct
22 Correct 155 ms 156584 KB Output is correct
23 Correct 152 ms 156584 KB Output is correct
24 Correct 151 ms 156584 KB Output is correct
25 Correct 159 ms 156584 KB Output is correct
26 Correct 162 ms 156964 KB Output is correct
27 Correct 225 ms 159832 KB Output is correct
28 Correct 204 ms 159832 KB Output is correct
29 Incorrect 309 ms 164076 KB Output isn't correct
30 Halted 0 ms 0 KB -