oj.uz

Submission #563737

# Submission time Handle Problem Language Result Execution time Memory
563737 2022-05-18T04:44:17 Z hohohaha Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 654 ms 60408 KB 
#include<bits/stdc++.h>
using namespace std;

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define em emplace
#define sp ' '
#define endl '\n'
//#define int long long

#define ld long double

const int maxn = 1e6 + 5; 

int n; 
vi g[maxn]; 
int m, t;
bool in[maxn]; 
int dp[maxn]; 
int pref[maxn]; 
void mark(int u, int p, int des) { 
	if(u == des) { 
	 	in[u] = 1; 
	 	return; 
	 }
	for(int v: g[u]) { 
		if(v - p) { 
			mark(v, u, des);
			in[u] |= in[v]; 
		}
	}
}
			

void dfs_solve(int u, int p) { 	
	if(g[u].size() == 1) {
		dp[u] = 0; 
	}
	else {
    	int mx = 0, mx2 = 0; 
    	for(int v: g[u]) { 
    		if(v == p) continue; 
    		dfs_solve(v, u); 
    		if(dp[v] > mx) { 
    			mx2 = mx; 
    			mx = dp[v]; 
    		}
    		else if(dp[v] > mx2) { 
    			mx2 = dp[v]; 
    		}
    	}
    	dp[u] = g[u].size() + mx2 - 1; 
	}
}

int dfs_solve_2(int u, int p) {
	int nxt = -1; 
	for(int v: g[u]) if(v - p and in[v]) nxt = v; 
	if(nxt == -1) return 0; 

	int temp = dfs_solve_2(nxt, u); 
	pref[u] = pref[nxt]; 
	
	int mx = 0, mx2 = 0; 
	for(int v: g[u]) { 
		if(!in[v]) { 
			pref[u]++;
			if(dp[v] > mx) { 
				mx2 = mx; 
				mx = dp[v]; 
			}
			else if(dp[v] > mx2) { 
				mx2 = dp[v]; 
			}
		}
	}
	
	//cout << mx2 << sp << pref[u] << endl;  
	
	return min(max(mx2 + pref[u], temp + 1), max(mx + pref[u], temp)); 
}

signed main() { 
	//freopen("mousetrap.inp", "r", stdin); 
//	freopen("mousetrap.out", "w", stdout); 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	
	cin >> n >> t >> m; 
	fori(i, 1, n - 1) { 
	 	int u, v; cin >> u >> v; 
	 	g[u].eb(v); 
	 	g[v].eb(u); 
	 }
	 
	mark(t, t, m); 
	
	fori(i, 1, n) { 
		if(in[i]) {
			//cout << i << sp;  
			for(int j: g[i]) {
				if(!in[j]) {
					dfs_solve(j, i); 
				}
			}
		}
	}
	assert(g[m].size() != 1); 
	cout << dfs_solve_2(m, m); 
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 48084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 59132 KB Output is correct
2 Correct 244 ms 55496 KB Output is correct
3 Correct 651 ms 60408 KB Output is correct
4 Correct 296 ms 41988 KB Output is correct
5 Correct 640 ms 60104 KB Output is correct
6 Correct 654 ms 60208 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 48084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 48084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -