oj.uz

Submission #490963

# Submission time Handle Problem Language Result Execution time Memory
490963 2021-11-30T02:16:51 Z generic_placeholder_name Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 672 ms 73320 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

constexpr int N = 1e6 + 5;
bool path[N];
vi adj[N];
int dp[N];

void dfs(int u, int p = -1) {
    int sum = 0, mx = -1, cnt = 0;
    for(int v: adj[u]) if(v != p) {
         dfs(v, u);
         if(!path[v]) {
            sum += dp[v];
            mx = max(mx, dp[v]);
            cnt++;
         }
         else path[u] = 1;
    }
    if(!cnt) dp[u] = 0;
    else dp[u] = sum - mx + cnt;
}

int32_t main() {
    fastio;
    int n, t, m; cin >> n >> t >> m; --t, --m;
    path[m] = 1;
    rep(_, n - 1) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].eb(v);
        adj[v].eb(u);
    }
    dfs(t);
    int ans = 0;
    rep(i, n) if(path[i] && i != t) ans += dp[i];
    cout << ans << endl;
}

Compilation message

mousetrap.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("unroll-loops")
      |

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23812 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23784 KB Output is correct
5 Incorrect 15 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 72380 KB Output is correct
2 Correct 236 ms 67392 KB Output is correct
3 Incorrect 672 ms 73320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23812 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23784 KB Output is correct
5 Incorrect 15 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23812 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23784 KB Output is correct
5 Incorrect 15 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -