oj.uz

Submission #563706

# Submission time Handle Problem Language Result Execution time Memory
563706 2022-05-18T03:20:44 Z hohohaha Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 600 ms 60168 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;
int dp[maxn]; 

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; 
	}
}

signed main() { 
//	freopen("oneway.inp", "r", stdin); 
//	freopen("oneway.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); 
	 }
	if(count(begin(g[t]), end(g[t]), m)) {
		 dfs_solve(m, t); 
		cout << dp[m];  
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 58912 KB Output is correct
2 Correct 241 ms 55536 KB Output is correct
3 Correct 600 ms 60076 KB Output is correct
4 Correct 277 ms 42008 KB Output is correct
5 Correct 600 ms 60168 KB Output is correct
6 Correct 596 ms 60108 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -