제출 #46948

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46948		zscoder	Wild Boar (JOI18_wild_boar)	C++17	62 / 100	18057 ms	741424 KiB

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 dp[2][5];
ll D[2111][2111][5];
vector<pair<int,int> > paths[2111][2111];
vector<ll> W;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	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);
	}
	/*
	int orim = m;
	for(int i=0;i<n;i++)
	{
		adj[n].pb(mp(mp(i,0),m++)); edges.pb({n,i}); W.pb(0);
	}
	*/
	int orim = m; 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();
			//cerr<<"DIST : "<<s<<' '<<u<<' '<<d<<'\n';
			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(edges[id][0]!=v) vid++;
				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; //D[j][i][0] = mn;
			paths[i][j].pb(cur); //paths[j][i].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					//cerr<<"OUT "<<i<<' '<<j<<' '<<k<<' '<<l<<'\n';
					if(edges[k].se!=paths[i][j][0].fi&&dist[k][l]+W[k]+W[l]<mn)
					{
						//cerr<<"OUT 2 : "<<i<<' '<<j<<' '<<k<<' '<<l<<'\n';
						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; //= D[j][i][1] = mn;
			paths[i][j].pb(cur); //paths[j][i].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; //D[j][i][2] = mn;
			paths[i][j].pb(cur); //paths[j][i].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; // D[j][i][3] = mn;
			paths[i][j].pb(cur); //paths[j][i].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; //D[j][i][2] = mn;
			paths[i][j].pb(cur); //paths[j][i].pb(cur);
		}
	}
	for(int i=0;i<L;i++)
	{
		cin>>a[i]; a[i]--;
	}
	for(int zz=0;zz<q;zz++)
	{
		int y,z; cin>>y>>z; y--; z--; a[y]=z;
		/*
		for(int i=0;i<m*2;i++)
		{
			dp[0][i] = INF;
		}
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<2;j++)
			{
				if(edges[i][j]==a[0])
				{
					dp[0][getid(i,j)] = 0;
				}
			}
		}
		*/
		/*
		dp[0][getid(orim + a[0],1)] = 0;
		for(int i=0;i+1<L;i++)
		{
			int pre = i&1; int cur = pre^1;
			for(int j=0;j<m*2;j++)
			{
				dp[cur][j] = INF;
			}
			for(int j=0;j<m*2;j++)
			{
				if(dp[pre][j]<INF)
				{
					ll v=dp[pre][j];
					for(int k:belong[a[i+1]])
					{
						if(dist[j][k]<INF)
						{
							dp[cur][k] = min(dp[cur][k], v + dist[j][k]);
						}
					}
				}
			}
		}
		ll mn = INF;
		for(int i=0;i<m*2;i++)
		{
			mn = min(mn, dp[(L+1)&1][i]);
		}
		
		cout<<mn<<'\n';
		*/
		for(int i=0;i<5;i++) dp[1][i] = D[a[0]][a[1]][i];
		/*
		for(int j=0;j<5;j++)
		{
			cerr<<0<<' '<<j<<' '<<paths[a[0]][a[1]][j].fi<<' '<<paths[a[0]][a[1]][j].se<<' '<<dp[1][j]<<'\n';
		}
		*/
		for(int i=1;i+1<L;i++)
		{
			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++)
					{
						//cerr<<i<<' '<<j<<' '<<k<<' '<<paths[a[i-1]][a[i]][j].fi<<' '<<paths[a[i-1]][a[i]][j].se<<' '<<paths[a[i]][a[i+1]][k].fi<<' '<<paths[a[i]][a[i+1]][k].se<<' '<<D[a[i-1]][a[i]][j]<<' '<<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)
						{
							dp[cur][k] = min(dp[cur][k], v + D[a[i]][a[i+1]][k]);
						}
					}
				}
			}
			/*
			for(int j=0;j<5;j++)
			{
				cerr<<i<<' '<<j<<' '<<paths[a[i]][a[i+1]][j].fi<<' '<<paths[a[i]][a[i+1]][j].se<<' '<<dp[cur][j]<<'\n';
			}
			*/
		}
		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';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:74:9: warning: unused variable 'v' [-Wunused-variable]
     int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
         ^
wild_boar.cpp:76:32: warning: unused variable 'v1' [-Wunused-variable]
     int u1 = edges[id].fi; int v1 = edges[id].se;
                                ^~
wild_boar.cpp:59:6: warning: unused variable 'orim' [-Wunused-variable]
  int orim = m; m*=2;
      ^~~~

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 0 / 38