답안 #46963 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46963	2018-04-25T13:03:44 Z	zscoder	Wild Boar (JOI18_wild_boar)	C++17	12 / 100	310 ms	164452 KB

wild_boar

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #46963

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0