Submission #522318

#	Time	Username	Problem	Language	Result	Execution time	Memory
522318		new_acc	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	3 ms	3020 KiB

crocodile

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (int)(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
vector<pair<int,ll> > graf[N];
bool vis[N],wyb[N];
ll dp[N];
void dfs(int v){
	vis[v]=1;
	vector<pair<int,ll> >curr;
	for(auto u:graf[v]){
		if(vis[u.fi]) continue;	
		curr.push_back({u.fi,u.se});
		dfs(u.fi);
	}
	ll naj1=LLONG_MAX,naj2=LLONG_MAX;
	for(auto u:curr){
		if(dp[u.fi]+u.se<=naj1){
			naj2=min(naj2,naj1);
			naj1=dp[u.fi]+u.se;
		}else naj2=min(naj2,dp[u.fi]+u.se);
	}
	dp[v]=naj2;
	if(wyb[v]) dp[v]=0;
}
ll travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
	rep(i,m) graf[r[i][0]].push_back({r[i][1],l[i]}),graf[r[i][1]].push_back({r[i][0],l[i]});
	rep(i,k) wyb[p[i]]=1;
	dfs(0);
	return dp[0];
}
/*int main(){
	int r[7][2];
	r[0][0]=0,r[0][1]=2;
	r[1][0]=0,r[1][1]=3;
	r[2][0]=3,r[2][1]=2;
	r[3][0]=2,r[3][1]=1;
	r[4][0]=0,r[4][1]=1;
	r[5][0]=0,r[5][1]=4;
	r[6][0]=3,r[6][1]=4;
	int l[7];
	l[0]=4,l[1]=3,l[2]=2,l[3]=10,l[4]=100,l[5]=7,l[6]=9;
	int p[2];
	p[0]=1,p[1]=3;
	cout<<travel_plan(5,6,r,l,2,p)<<"\n";
}*/

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