제출 #1177145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177145		alexander707070	봉쇄 시간 (IOI23_closing)	C++20	8 / 100	95 ms	61876 KiB

closing

#include<bits/stdc++.h>
//#include "closing.h"

#define MAXN 1000007
using namespace std;

struct event{
	long long cost;
	int x,type;

	inline friend bool operator < (event fr,event sc){
		return fr.cost>sc.cost;
	}
};

int n,x,y;
vector< pair<int,int> > v[MAXN];
long long dist[MAXN][2];
int vis[MAXN];

bool reach[MAXN][2];

priority_queue< event > q;

void dfs(int x,int p,int id,long long d){
	dist[x][id]=d;
	q.push({dist[x][id],x,id});

	for(auto nxt:v[x]){
		if(nxt.first==p)continue;
		dfs(nxt.first,x,id,d+nxt.second);
	}
}

void bfs(int x,int id){
	for(auto nxt:v[x]){
		if(reach[nxt.first][id])continue;

		reach[nxt.first][id]=true;
		if(vis[nxt.first]>0){
			q.push({dist[nxt.first][id] - dist[nxt.first][1-id],nxt.first,id});
		}
	}
}

int max_score(int N, int X, int Y, long long K,vector<int> U, vector<int> V, vector<int> W){
	n=N; x=X+1; y=Y+1;

	for(int i=1;i<=n;i++){
		v[i].clear();
		vis[i]=0;
		reach[i][0]=reach[i][1]=false;
	}

	while(!q.empty())q.pop();

	for(int i=0;i<n-1;i++){
		v[U[i]+1].push_back({V[i]+1,W[i]});
		v[V[i]+1].push_back({U[i]+1,W[i]});
	}

	dfs(x,0,0,0);
	dfs(y,0,1,0);

	int ans=0;

	reach[x][0]=true;
	reach[y][1]=true;

	while(!q.empty() and K>0){
		event curr=q.top();
		q.pop();

		if(curr.cost>K)break;
		if(vis[curr.x]==3)continue;

		bfs(curr.x,curr.type);

		if(vis[curr.x]>0){
			vis[curr.x]=3;
		}else{
			vis[curr.x]=curr.type+1;
			if(reach[curr.x][1-curr.type])q.push({dist[curr.x][1-curr.type] - curr.cost,1-curr.type});
		}

		K-=curr.cost; ans++;
	}

	return ans;
}

/*int main(){

	//cout<<max_score(7, 0, 2, 10, {0, 0, 1, 2, 2, 5}, {1, 3, 2, 4, 5, 6}, {2, 3, 4, 2, 5, 3})<<"\n";	
	//cout<<max_score(4, 0, 3, 20, {0, 1, 2}, {1, 2, 3}, {18, 1, 19})<<"\n";  
	
	return 0;
}*/

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17