oj.uz

답안 #40068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40068 2018-01-26T10:24:02 Z KtlTheBest Torrent (COI16_torrent) C++14
0 / 100
 106 ms 15108 KB 
/**
 	Template created by Danel Batyrbek
 	All rights are reserved 2018 (lol)
*/

#include <bits/stdc++.h>

#define speed_up ios_base :: sync_with_stdio(0);cin.tie(0)
#define fr first
#define sc second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define all(x) x.begin(), x.end()
#define debug(x) cerr << x << '\n';
#define YES "YES"
#define NO "NO"
#define skip continue
#define left(x) x << 1
#define rght(x) x << 1 | 1
#define forn(x, y, z) for(int x = y; x <= z; ++ x)
#define for1(x, y, z) for(int x = y; x >= z; -- x)
#define fname ""
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef double ld;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int N3 = 1e3 + 10;
const int INF = 2e9 + 10;
const ll LINF = 2e18;

int n, a, b, cnt1[N], cnt2[N], dp[N], ans;
bool u[N];
vector <pii> v1[N], v2[N];
queue <pii> q;

void init(){
	forn(i, 1, n) u[i] = 0;
}

void dfs(int x, vector <pii> v[], int arr[]){
	u[x] = 1;
	for(pii to : v[x]){
		if(!u[to.sc]){
			dfs(to.sc, v, arr);
			arr[x] += arr[to.sc];
		}
	}
	arr[x] ++;
}

int main(){
#ifdef DEBUG
	freopen("in", "r", stdin);
#else	                    
	if(fname != ""){
	freopen(fname".in", "r", stdin);
	freopen(fname".out", "w", stdout);
	}
#endif
	cin >> n >> a >> b;
	forn(i, 1, n - 1){
		dp[i] = INF;
		int x, y;
		cin >> x >> y;
		v1[x].pb(mkp(0, y));
		v1[y].pb(mkp(0, x));
		v2[x].pb(mkp(0, y));
		v2[y].pb(mkp(0, x));
	}

	dp[n] = INF;

	dfs(a, v1, cnt1);
	init();
	dfs(b, v2, cnt2);

	forn(i, 1, n){
		for(pii x : v1[i]){
			x.fr = -cnt1[x.sc];
		}
		for(pii x : v2[i]){
			x.fr = -cnt2[x.sc];
		}
		sort(all(v1[i]));
		sort(all(v2[i]));
	}

	q.push(mkp(a, a));
	q.push(mkp(b, b));

	dp[a] = dp[b] = 0;

	while(q.size()){
		pii x = q.front();
		q.pop();
		int cnt = 1;
		if(x.sc == a){
			for(pii to : v1[x.fr]){
				if(dp[to.sc] > dp[x.fr] + cnt){
					dp[to.sc] = dp[x.fr] + cnt;
					cnt ++;
					q.push(mkp(to.sc, a));
				}
			}
		} else {
		    for(pii to : v2[x.fr]){
				if(dp[to.sc] > dp[x.fr] + cnt){
					dp[to.sc] = dp[x.fr] + cnt;
					cnt ++;
					q.push(mkp(to.sc, b));
				}
			}
		}
	}

	forn(i, 1, n) ans = max(ans, dp[i]);
	cout << ans;
	return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:61:14: warning: comparison with string literal results in unspecified behaviour [-Waddress]
  if(fname != ""){
              ^
torrent.cpp:62:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen(fname".in", "r", stdin);
                                 ^
torrent.cpp:63:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen(fname".out", "w", stdout);
                                   ^

Subtask #1
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 8112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 106 ms 15108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -