Submission #866408

#	Time	Username	Problem	Language	Result	Execution time	Memory
866408		GoldLight	악어의 지하 도시 (IOI11_crocodile)	C++17	89 / 100	410 ms	66712 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
 
//const int NN=1e5;
const long long INF=1e18;
// int R[NN+1][2], L[NN+1], P[NN+1];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	vector<pair<int,int>> v[N];
	for(int i=0; i<M; i++){
		v[R[i][0]].push_back({R[i][1], L[i]});
		v[R[i][1]].push_back({R[i][0], L[i]});
	}
	vector<vector<long long>> dist(N+2, vector<long long>(2, INF));
	priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
	for(int i=0; i<K; i++){
		dist[P[i]][0]=dist[P[i]][1]=0;
		pq.push({0, P[i]});
	}
	while(!pq.empty()){
		auto[d, u]=pq.top(); pq.pop();
		if(d>dist[u][1]) continue;
		for(auto [to, di]:v[u]){
			if(d+di<dist[to][1]){
				dist[to][1]=d+di;
				sort(dist[to].begin(), dist[to].end());
				if(dist[to][1]<INF) pq.push({dist[to][1], to});
			}
		}
	}
	return dist[0][1];
}
// int main(){
// 	fast();
// 	int n, m, k; cin>>n>>m>>k;
// 	for(int i=0; i<m; i++){
// 		cin>>R[i][0]>>R[i][1];
// 	}
// 	for(int i=0; i<m; i++) cin>>L[i];
// 	for(int i=0; i<k; i++) cin>>P[i];
// 	cout<<travel_plan(n, m, k);
// }
 
/*
#define int long long
const int INF=1e18;
signed main(){
	fast();
	int teskes; cin>>teskes;
	while(teskes--){
		int n, m, k; cin>>n>>m>>k;
		int a[n+1], now=0;
		for(int i=1; i<=n; i++) cin>>a[i];
		vector<pair<int,int>> v[n+1], to(2*k+5);
		vector<int> dp(2*k+5, -INF);
		dp[0]=0;
		v[1].push_back({1, now++});  
		for(int i=1; i<=k; i++){
			int a, b, c, d, h; cin>>a>>b>>c>>d>>h;
			v[a].push_back({b, now++});
			v[c].push_back({d, now++});
			to[now-2]={now-1, h};
		}
		v[n].push_back({m, now});
		for(int i=1; i<=n; i++){
			int sz=v[i].size();
			sort(v[i].begin(), v[i].end());
			for(int j=1; j<sz; j++){
				dp[v[i][j].second]=max(dp[v[i][j].second], dp[v[i][j-1].second]-(v[i][j].first-v[i][j-1].first)*a[i]);
			}
			for(int j=sz-2; j>=0; j--){
				dp[v[i][j].second]=max(dp[v[i][j].second], dp[v[i][j+1].second]-(v[i][j+1].first-v[i][j].first)*a[i]);
			}
			for(auto [r, num]:v[i]){
				if(to[num].first && dp[num]!=-INF){
					dp[to[num].first]=max(dp[to[num].first], dp[num]+to[num].second);
				}
			}
		}
		if(dp[now]==-INF) cout<<"NO ESCAPE";
		else cout<<-dp[now];
		cout<<'\n';
	}
}
*/
/*
#define int long long
const int INF=1e18, N=3e5;
signed main(){
	fast();
	int teskes; cin>>teskes;
	while(teskes--){
		int n, m, k; cin>>n>>m>>k;
		int a[n+1], num=2;
		for(int i=1; i<=n; i++) cin>>a[i];
		map<pair<int,int>, int> mp; mp[{1, 1}]=0, mp[{n, m}]=1;
		vector<pair<int,int>> v[N+1];
		priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
		pq.push({1, 1}), pq.push({n, m});
		for(int i=1; i<=k; i++){
			int p, q, r, s, h; cin>>p>>q>>r>>s>>h;
			if(!mp.count({p, q})) mp[{p, q}]=num++;
			if(!mp.count({r, s})) mp[{r, s}]=num++;
			v[mp[{p, q}]].push_back({mp[{r, s}], -h});
			pq.push({p, q});
			pq.push({r, s});
		}
		int la=pq.top().first, lb=pq.top().second; pq.pop();
		while(!pq.empty()){
			auto[na, nb]=pq.top(); pq.pop(); //new
			if(la==na && lb==nb) continue;
			if(la==na){
				v[mp[{la, lb}]].push_back({mp[{na, nb}], (nb-lb)*a[la]});
				v[mp[{na, nb}]].push_back({mp[{la, lb}], (nb-lb)*a[la]});
			}
			la=na, lb=nb;
		}
		vector<int> dist(num, INF);
		vector<bool> vis(num);
		dist[0]=0;
		pq.push({0, 0});
		while(!pq.empty()){
			auto[d, u]=pq.top(); pq.pop();
			if(vis[u]) continue;
			vis[u]=true;
			cout<<d<<' '<<u<<'\n';
			for(auto &[to, h]:v[u]){
				if(!vis[to] && dist[u]+h<dist[to]){
					dist[to]=dist[u]+h;
					pq.push({dist[to], to});
				}
			}
		}
		cout<<'\n';
		for(auto [x, y]:mp) cout<<x.first<<' '<<x.second<<' '<<y<<'\n';
		cout<<'\n';
		// for(auto [x, y]:mp){
		// 	cout<<x.first<<' '<<x.second<<" : ";
		// 	for(auto [node, val]:v[y]) cout<<node<<' ';
		// 	cout<<'\n';
		// }
		// if(dist[1]==INF) cout<<"NO ESCAPE";
		// else cout<<dist[1];
		// cout<<'\n';
	}
}*/

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 0 / 11