oj.uz

Submission #46963

# Submission time Handle Problem Language Result Execution time Memory
46963 2018-04-25T13:03:44 Z zscoder Wild Boar (JOI18_wild_boar) C++17
12 / 100
 310 ms 164452 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[262000];

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<262000;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 143 ms 156536 KB Output is correct
2 Correct 150 ms 156624 KB Output is correct
3 Correct 145 ms 156724 KB Output is correct
4 Correct 147 ms 156724 KB Output is correct
5 Correct 142 ms 156724 KB Output is correct
6 Correct 144 ms 156732 KB Output is correct
7 Correct 143 ms 156732 KB Output is correct
8 Correct 144 ms 156868 KB Output is correct
9 Correct 140 ms 156868 KB Output is correct
10 Correct 140 ms 156868 KB Output is correct
11 Correct 147 ms 156868 KB Output is correct
12 Correct 142 ms 156868 KB Output is correct
13 Correct 141 ms 156868 KB Output is correct
14 Correct 146 ms 156932 KB Output is correct
15 Correct 142 ms 156932 KB Output is correct
16 Correct 149 ms 156932 KB Output is correct
17 Correct 144 ms 156932 KB Output is correct
18 Correct 162 ms 156932 KB Output is correct
19 Correct 142 ms 156932 KB Output is correct
20 Correct 146 ms 156932 KB Output is correct
21 Correct 144 ms 156932 KB Output is correct
22 Correct 148 ms 156932 KB Output is correct
23 Correct 153 ms 156932 KB Output is correct
24 Correct 143 ms 156932 KB Output is correct
25 Correct 153 ms 156932 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 156536 KB Output is correct
2 Correct 150 ms 156624 KB Output is correct
3 Correct 145 ms 156724 KB Output is correct
4 Correct 147 ms 156724 KB Output is correct
5 Correct 142 ms 156724 KB Output is correct
6 Correct 144 ms 156732 KB Output is correct
7 Correct 143 ms 156732 KB Output is correct
8 Correct 144 ms 156868 KB Output is correct
9 Correct 140 ms 156868 KB Output is correct
10 Correct 140 ms 156868 KB Output is correct
11 Correct 147 ms 156868 KB Output is correct
12 Correct 142 ms 156868 KB Output is correct
13 Correct 141 ms 156868 KB Output is correct
14 Correct 146 ms 156932 KB Output is correct
15 Correct 142 ms 156932 KB Output is correct
16 Correct 149 ms 156932 KB Output is correct
17 Correct 144 ms 156932 KB Output is correct
18 Correct 162 ms 156932 KB Output is correct
19 Correct 142 ms 156932 KB Output is correct
20 Correct 146 ms 156932 KB Output is correct
21 Correct 144 ms 156932 KB Output is correct
22 Correct 148 ms 156932 KB Output is correct
23 Correct 153 ms 156932 KB Output is correct
24 Correct 143 ms 156932 KB Output is correct
25 Correct 153 ms 156932 KB Output is correct
26 Correct 148 ms 157296 KB Output is correct
27 Correct 216 ms 160248 KB Output is correct
28 Correct 213 ms 160248 KB Output is correct
29 Incorrect 310 ms 164452 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 156536 KB Output is correct
2 Correct 150 ms 156624 KB Output is correct
3 Correct 145 ms 156724 KB Output is correct
4 Correct 147 ms 156724 KB Output is correct
5 Correct 142 ms 156724 KB Output is correct
6 Correct 144 ms 156732 KB Output is correct
7 Correct 143 ms 156732 KB Output is correct
8 Correct 144 ms 156868 KB Output is correct
9 Correct 140 ms 156868 KB Output is correct
10 Correct 140 ms 156868 KB Output is correct
11 Correct 147 ms 156868 KB Output is correct
12 Correct 142 ms 156868 KB Output is correct
13 Correct 141 ms 156868 KB Output is correct
14 Correct 146 ms 156932 KB Output is correct
15 Correct 142 ms 156932 KB Output is correct
16 Correct 149 ms 156932 KB Output is correct
17 Correct 144 ms 156932 KB Output is correct
18 Correct 162 ms 156932 KB Output is correct
19 Correct 142 ms 156932 KB Output is correct
20 Correct 146 ms 156932 KB Output is correct
21 Correct 144 ms 156932 KB Output is correct
22 Correct 148 ms 156932 KB Output is correct
23 Correct 153 ms 156932 KB Output is correct
24 Correct 143 ms 156932 KB Output is correct
25 Correct 153 ms 156932 KB Output is correct
26 Correct 148 ms 157296 KB Output is correct
27 Correct 216 ms 160248 KB Output is correct
28 Correct 213 ms 160248 KB Output is correct
29 Incorrect 310 ms 164452 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 156536 KB Output is correct
2 Correct 150 ms 156624 KB Output is correct
3 Correct 145 ms 156724 KB Output is correct
4 Correct 147 ms 156724 KB Output is correct
5 Correct 142 ms 156724 KB Output is correct
6 Correct 144 ms 156732 KB Output is correct
7 Correct 143 ms 156732 KB Output is correct
8 Correct 144 ms 156868 KB Output is correct
9 Correct 140 ms 156868 KB Output is correct
10 Correct 140 ms 156868 KB Output is correct
11 Correct 147 ms 156868 KB Output is correct
12 Correct 142 ms 156868 KB Output is correct
13 Correct 141 ms 156868 KB Output is correct
14 Correct 146 ms 156932 KB Output is correct
15 Correct 142 ms 156932 KB Output is correct
16 Correct 149 ms 156932 KB Output is correct
17 Correct 144 ms 156932 KB Output is correct
18 Correct 162 ms 156932 KB Output is correct
19 Correct 142 ms 156932 KB Output is correct
20 Correct 146 ms 156932 KB Output is correct
21 Correct 144 ms 156932 KB Output is correct
22 Correct 148 ms 156932 KB Output is correct
23 Correct 153 ms 156932 KB Output is correct
24 Correct 143 ms 156932 KB Output is correct
25 Correct 153 ms 156932 KB Output is correct
26 Correct 148 ms 157296 KB Output is correct
27 Correct 216 ms 160248 KB Output is correct
28 Correct 213 ms 160248 KB Output is correct
29 Incorrect 310 ms 164452 KB Output isn't correct
30 Halted 0 ms 0 KB -