제출 #321517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321517		M_W	Torrent (COI16_torrent)	C++14	0 / 100	787 ms	66156 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
int dist[300300];
map<ii, ii> mp;
vector<int> adj[300300];
bool vis[300300];
int N, A, B;

ii dfs(int a){
	vis[a] = true;
	int ret = 0;
	set<ii> s;
	for(auto x : adj[a]){
		if(vis[x] || x == B) continue;
		s.insert(dfs(x));
	}
	
	int ia = s.size();
	for(auto x : s){
		mp[make_pair(a, x.second)].first = ia;
		mp[make_pair(x.second, a)].first = ia;
		ret = max(x.first + ia, ret);
		ia--;
	}
	return make_pair(ret, a);
}

ii dfs2(int a){
	vis[a] = true;
	int ret = 0;
	set<ii> s;
	for(auto x : adj[a]){
		if(vis[x] || x == A) continue;
		s.insert(dfs2(x));
	}
	
	int ia = s.size();
	for(auto x : s){
		mp[make_pair(a, x.second)].second = ia;
		mp[make_pair(x.second, a)].second = ia;
		ret = max(x.first + ia, ret);
		ia--;
	}
	return make_pair(ret, a);
}

void updist(int a, int w){
	vis[a] = true;
	dist[a] = min(dist[a], w);
	for(auto x : adj[a]){
		if(vis[x]) continue;
		int tmp = mp[make_pair(a, x)].first;
		if(tmp == 0) continue;
		updist(x, w + tmp);
	}
}

void updist2(int a, int w){
	vis[a] = true;
	dist[a] = min(dist[a], w);
	for(auto x : adj[a]){
		if(vis[x]) continue;
		int tmp = mp[make_pair(a, x)].second;
		if(tmp == 0) continue;
		updist2(x, w + tmp);
	}
}

int main(){
	scanf("%d %d %d", &N, &A, &B);
	for(int i = 1, u, v; i < N; i++){
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(A);
	memset(vis, 0, sizeof vis);
	dfs2(B);
	memset(vis, 0, sizeof vis);
	
	for(int i = 1; i <= N; i++)
		dist[i] = INT_MAX;
	
	updist(A, 0);
	memset(vis, 0, sizeof vis);
	updist2(B, 0);
	
	int ans = INT_MIN;
	for(int i = 1; i <= N; i++){
		ans = max(ans, dist[i]);
	}	
		
	printf("%d", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

torrent.cpp: In function 'int main()':
torrent.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d %d %d", &N, &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69