Submission #946640

#	Time	Username	Problem	Language	Result	Execution time	Memory
946640		StefanSebez	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	2090 ms	6748 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int N=1e5+50;
const ll inf=1e18;
vector<pair<int,ll> >E[N];
map<pair<int,int>,bool>mapa;
map<pair<int,int>,ll>grana;
int deg[N],dp[N];
bool nesto[N],was[N],trenutno[N];
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
	for(int i=0;i<m;i++){
		E[R[i][0]].pb({R[i][1],L[i]}),E[R[i][1]].pb({R[i][0],L[i]});
		deg[R[i][0]]++,deg[R[i][1]]++;
		grana[{R[i][0],R[i][1]}]=grana[{R[i][1],R[i][0]}]=L[i];
	}
	for(int i=0;i<K;i++) nesto[P[i]]=true,dp[P[i]]=0;
	set<int>pored;
	for(int i=0;i<n;i++){
		if(nesto[i]){
			trenutno[i]=true;
			for(auto j:E[i]) if(!nesto[j.fi]) pored.insert(j.fi);
		}
	}
	//for(auto i=pored.begin();i!=pored.end();i++) printf("%i ",*i);
	//printf("\n");
	dp[0]=-1;
	while(dp[0]==-1){
		int U=-1,mn=1e9;
		for(auto i=pored.begin();i!=pored.end();i=next(i)){
			vector<pair<int,int> >temp;
			int u=*i;
			for(auto j:E[u]){
				if(trenutno[j.fi]) temp.pb({j.se+dp[j.fi],j.fi});
			}
			if(temp.size()>=2){
				sort(temp.begin(),temp.end());
				if(mn>temp[1].fi){
					U=u;
					mn=temp[1].fi;
				}
				/*dp[u]=temp[1].fi;
				for(auto j:temp){
					deg[j.se]--;
					deg[u]--;
				}
				was[*i]=true;
				pored.erase(*i);
				for(auto j:E[u]){
					if(deg[j.fi]>=2) pored.insert(j.fi);
				}
				break;*/
			}
		}
		//printf("%i %i\n",U,mn);
		vector<pair<int,int> >temp;
		int u=U;
		for(auto j:E[u]){
			if(trenutno[j.fi]) temp.pb({j.se+dp[j.fi],j.fi});
		}
		if(temp.size()>=2){
			sort(temp.begin(),temp.end());
			dp[u]=temp[1].fi;
			for(auto j:temp){
				deg[j.se]--;
				if(deg[j.se]==0) trenutno[j.se]=false,was[j.se]=true;
				deg[u]--;
				//printf("%i: %i\n%i: %i\n",j.se,deg[j.se],u,deg[u]);
			}
			//was[u]=true;
			trenutno[u]=true;
			pored.erase(u);
			for(auto j:E[u]){
				if(!was[j.fi]) pored.insert(j.fi);
			}
		}
		//printf("%i\n",pored.size());
		//for(auto i=pored.begin();i!=pored.end();i++) printf("%i ",*i);
		//printf("\n");
		//for(int i=0;i<n;i++) if(trenutno[i]) printf("%i ",i);
		//printf("\n");
	}
	return dp[0];
	/*int U=0;int res=0;
	while(!nesto[U]){
		//printf("%i\n",U);
		ll dist[n+10];int parent[n+10];
		memset(parent,-1,sizeof(parent));
		for(int i=0;i<n;i++) dist[i]=inf;
		dist[U]=0;
		priority_queue<pair<ll,int> >pq;
		pq.push({0,U});
		while(!pq.empty()){
			int u=pq.top().se;ll w=-pq.top().fi;
			pq.pop();
			if(w>dist[u]) continue;
			for(auto i:E[u]){
				if(mapa[{i.fi,u}]) continue;
				if(dist[i.fi]>dist[u]+i.se){
					dist[i.fi]=dist[u]+i.se;
					parent[i.fi]=u;
					pq.push({-dist[i.fi],i.fi});
				}
			}
		}
		//for(int i=0;i<n;i++) printf("%i: %i %i\n",i,dist[i],parent[i]);
		//printf("\n");
		int mn=0;
		for(int i=0;i<K;i++) if(dist[P[i]]<dist[P[mn]]) mn=i;
		int tmp=mn;mn=P[mn];
		//printf("%i %i\n",tmp,mn);
		while(parent[mn]!=U) mn=parent[mn];
		mapa[{U,mn}]=mapa[{mn,U}]=true;
		mn=0;if(tmp==0) mn=K-1;
		for(int i=0;i<K;i++) if(dist[P[i]]<dist[P[mn]] && i!=tmp) mn=i;
		mn=P[mn];
		while(parent[mn]!=U) mn=parent[mn];
		mapa[{U,mn}]=mapa[{mn,U}]=true;
		res+=grana[{U,mn}];
		U=mn;
		//printf("%i\n",mn);
	}
	return res;*/
}

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