답안 #46803 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46803	2018-04-23T14:50:31 Z	zscoder	Wild Boar (JOI18_wild_boar)	C++17	47 / 100	18000 ms	223344 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<vi> edges;
ll dist[6111][6111];
int n,m,q,L; 
vector<pair<ii,int> > adj[2111];

int getid(int a, int b)
{
	return (a*2+b);
}
const ll INF=ll(1e18);
int a[211111];
ll dp[2][6111];

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});
		adj[u].pb(mp(mp(v,w),i)); adj[v].pb(mp(mp(u,w),i));
	}
	int orim = m;
	for(int i=0;i<n;i++)
	{
		adj[n].pb(mp(mp(i,0),m++)); edges.pb({n,i});
	}
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<2;j++)
		{
			priority_queue<ii,vector<ii>,greater<ii> > pq;
			int s = getid(i,j);
			pq.push(mp(0,s));
			for(int k=0;k<m*2;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/2][u%2]; int edgeno = u/2;
				for(auto k:adj[vertex])
				{
					int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
					if(id==edgeno) continue;
					int vid = id*2;
					if(edges[id][0]!=v) vid++;
					if(dist[s][vid]>d+w)
					{
						dist[s][vid] = d + w;
						pq.push(mp(dist[s][vid], vid));
					}
				}
			}
		}
	}
	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=0;k<m*2;k++)
					{
						if(dist[j][k]<INF&&edges[k/2][k&1] == a[i+1])
						{
							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]);
		}
		if(mn>=INF) mn=-1;
		cout<<mn<<'\n';
	}
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	624 KB	Output is correct
3	Correct	2 ms	692 KB	Output is correct
4	Correct	2 ms	804 KB	Output is correct
5	Correct	3 ms	804 KB	Output is correct
6	Correct	2 ms	804 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	988 KB	Output is correct
9	Correct	2 ms	988 KB	Output is correct
10	Correct	2 ms	988 KB	Output is correct
11	Correct	2 ms	988 KB	Output is correct
12	Correct	2 ms	988 KB	Output is correct
13	Correct	2 ms	988 KB	Output is correct
14	Correct	2 ms	988 KB	Output is correct
15	Correct	2 ms	988 KB	Output is correct
16	Correct	2 ms	988 KB	Output is correct
17	Correct	2 ms	988 KB	Output is correct
18	Correct	3 ms	988 KB	Output is correct
19	Correct	2 ms	1008 KB	Output is correct
20	Correct	2 ms	1012 KB	Output is correct
21	Correct	2 ms	1012 KB	Output is correct
22	Correct	2 ms	1012 KB	Output is correct
23	Correct	2 ms	1012 KB	Output is correct
24	Correct	2 ms	1012 KB	Output is correct
25	Correct	2 ms	1012 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	624 KB	Output is correct
3	Correct	2 ms	692 KB	Output is correct
4	Correct	2 ms	804 KB	Output is correct
5	Correct	3 ms	804 KB	Output is correct
6	Correct	2 ms	804 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	988 KB	Output is correct
9	Correct	2 ms	988 KB	Output is correct
10	Correct	2 ms	988 KB	Output is correct
11	Correct	2 ms	988 KB	Output is correct
12	Correct	2 ms	988 KB	Output is correct
13	Correct	2 ms	988 KB	Output is correct
14	Correct	2 ms	988 KB	Output is correct
15	Correct	2 ms	988 KB	Output is correct
16	Correct	2 ms	988 KB	Output is correct
17	Correct	2 ms	988 KB	Output is correct
18	Correct	3 ms	988 KB	Output is correct
19	Correct	2 ms	1008 KB	Output is correct
20	Correct	2 ms	1012 KB	Output is correct
21	Correct	2 ms	1012 KB	Output is correct
22	Correct	2 ms	1012 KB	Output is correct
23	Correct	2 ms	1012 KB	Output is correct
24	Correct	2 ms	1012 KB	Output is correct
25	Correct	2 ms	1012 KB	Output is correct
26	Correct	4 ms	1364 KB	Output is correct
27	Correct	64 ms	4368 KB	Output is correct
28	Correct	63 ms	4912 KB	Output is correct
29	Correct	1053 ms	10472 KB	Output is correct
30	Correct	3525 ms	10940 KB	Output is correct
31	Correct	9971 ms	11040 KB	Output is correct
32	Correct	10039 ms	11240 KB	Output is correct
33	Correct	952 ms	13360 KB	Output is correct
34	Correct	833 ms	13900 KB	Output is correct
35	Correct	11835 ms	13996 KB	Output is correct
36	Correct	7971 ms	14180 KB	Output is correct
37	Correct	832 ms	14448 KB	Output is correct
38	Correct	733 ms	16700 KB	Output is correct
39	Correct	5827 ms	16912 KB	Output is correct
40	Correct	714 ms	17244 KB	Output is correct
41	Correct	707 ms	17588 KB	Output is correct
42	Correct	6325 ms	18816 KB	Output is correct
43	Correct	664 ms	20184 KB	Output is correct
44	Correct	725 ms	20540 KB	Output is correct
45	Correct	798 ms	23052 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	624 KB	Output is correct
3	Correct	2 ms	692 KB	Output is correct
4	Correct	2 ms	804 KB	Output is correct
5	Correct	3 ms	804 KB	Output is correct
6	Correct	2 ms	804 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	988 KB	Output is correct
9	Correct	2 ms	988 KB	Output is correct
10	Correct	2 ms	988 KB	Output is correct
11	Correct	2 ms	988 KB	Output is correct
12	Correct	2 ms	988 KB	Output is correct
13	Correct	2 ms	988 KB	Output is correct
14	Correct	2 ms	988 KB	Output is correct
15	Correct	2 ms	988 KB	Output is correct
16	Correct	2 ms	988 KB	Output is correct
17	Correct	2 ms	988 KB	Output is correct
18	Correct	3 ms	988 KB	Output is correct
19	Correct	2 ms	1008 KB	Output is correct
20	Correct	2 ms	1012 KB	Output is correct
21	Correct	2 ms	1012 KB	Output is correct
22	Correct	2 ms	1012 KB	Output is correct
23	Correct	2 ms	1012 KB	Output is correct
24	Correct	2 ms	1012 KB	Output is correct
25	Correct	2 ms	1012 KB	Output is correct
26	Correct	4 ms	1364 KB	Output is correct
27	Correct	64 ms	4368 KB	Output is correct
28	Correct	63 ms	4912 KB	Output is correct
29	Correct	1053 ms	10472 KB	Output is correct
30	Correct	3525 ms	10940 KB	Output is correct
31	Correct	9971 ms	11040 KB	Output is correct
32	Correct	10039 ms	11240 KB	Output is correct
33	Correct	952 ms	13360 KB	Output is correct
34	Correct	833 ms	13900 KB	Output is correct
35	Correct	11835 ms	13996 KB	Output is correct
36	Correct	7971 ms	14180 KB	Output is correct
37	Correct	832 ms	14448 KB	Output is correct
38	Correct	733 ms	16700 KB	Output is correct
39	Correct	5827 ms	16912 KB	Output is correct
40	Correct	714 ms	17244 KB	Output is correct
41	Correct	707 ms	17588 KB	Output is correct
42	Correct	6325 ms	18816 KB	Output is correct
43	Correct	664 ms	20184 KB	Output is correct
44	Correct	725 ms	20540 KB	Output is correct
45	Correct	798 ms	23052 KB	Output is correct
46	Correct	293 ms	27500 KB	Output is correct
47	Execution timed out	18087 ms	223344 KB	Time limit exceeded
48	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	624 KB	Output is correct
3	Correct	2 ms	692 KB	Output is correct
4	Correct	2 ms	804 KB	Output is correct
5	Correct	3 ms	804 KB	Output is correct
6	Correct	2 ms	804 KB	Output is correct
7	Correct	2 ms	828 KB	Output is correct
8	Correct	2 ms	988 KB	Output is correct
9	Correct	2 ms	988 KB	Output is correct
10	Correct	2 ms	988 KB	Output is correct
11	Correct	2 ms	988 KB	Output is correct
12	Correct	2 ms	988 KB	Output is correct
13	Correct	2 ms	988 KB	Output is correct
14	Correct	2 ms	988 KB	Output is correct
15	Correct	2 ms	988 KB	Output is correct
16	Correct	2 ms	988 KB	Output is correct
17	Correct	2 ms	988 KB	Output is correct
18	Correct	3 ms	988 KB	Output is correct
19	Correct	2 ms	1008 KB	Output is correct
20	Correct	2 ms	1012 KB	Output is correct
21	Correct	2 ms	1012 KB	Output is correct
22	Correct	2 ms	1012 KB	Output is correct
23	Correct	2 ms	1012 KB	Output is correct
24	Correct	2 ms	1012 KB	Output is correct
25	Correct	2 ms	1012 KB	Output is correct
26	Correct	4 ms	1364 KB	Output is correct
27	Correct	64 ms	4368 KB	Output is correct
28	Correct	63 ms	4912 KB	Output is correct
29	Correct	1053 ms	10472 KB	Output is correct
30	Correct	3525 ms	10940 KB	Output is correct
31	Correct	9971 ms	11040 KB	Output is correct
32	Correct	10039 ms	11240 KB	Output is correct
33	Correct	952 ms	13360 KB	Output is correct
34	Correct	833 ms	13900 KB	Output is correct
35	Correct	11835 ms	13996 KB	Output is correct
36	Correct	7971 ms	14180 KB	Output is correct
37	Correct	832 ms	14448 KB	Output is correct
38	Correct	733 ms	16700 KB	Output is correct
39	Correct	5827 ms	16912 KB	Output is correct
40	Correct	714 ms	17244 KB	Output is correct
41	Correct	707 ms	17588 KB	Output is correct
42	Correct	6325 ms	18816 KB	Output is correct
43	Correct	664 ms	20184 KB	Output is correct
44	Correct	725 ms	20540 KB	Output is correct
45	Correct	798 ms	23052 KB	Output is correct
46	Correct	293 ms	27500 KB	Output is correct
47	Execution timed out	18087 ms	223344 KB	Time limit exceeded
48	Halted	0 ms	0 KB	-

답안 #46803

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0