oj.uz

답안 #907558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907558 2024-01-15T20:57:02 Z sysia Star Trek (CEOI20_startrek) C++17
23 / 100
 1000 ms 29748 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void solve(){
    int n, d; cin >> n >> d;
    //n <= 100, d = 1;
    vector<vector<int>>g(n+1);
    for (int i = 1; i<n; i++){
        int a, b; cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector dp(n+1, vector<int>(2));
    //jak jestesmy w lisciu w tak ukorzenionym drzewie to przegrywamy
    vector<int>depth(n+1), par(n+1);
    function<void(int, int)>dfs = [&](int v, int pa){
        par[v] = pa;
        dp[v][0] = 0;
        dp[v][1] = 1; //gracz 1 jest teraz w v i musi zrobic ruch, ale nie ma gdzie :p
        for (auto x: g[v]){
            if (x == pa) continue;
            depth[x] = depth[v]+1;
            dfs(x, v);
            dp[v][0] |= dp[x][1]; //musi byc jakas wygrywajaca
            dp[v][1] &= (dp[x][0] == 1); //musi prowadzic do samych wygrywajacych
        }
        debug(v, dp[v]);
    };
    vector win(n+1, vector<int>(2));
    for (int i = 1; i<=n; i++){
        dp.assign(n+1, vector<int>(2, 0));
        depth.assign(n+1, 0);
        dfs(i, i);
        win[i] = dp[i];
        // return;
    }
    depth[1] = 0;
    dfs(1, 1);
    int ans = 0;
    for (int i = 1; i<=n; i++){

        vector<int>path;
        int v = i;
        while (1){
            path.emplace_back(v);
            if (v == 1) break;
            v = par[v];
        }
        reverse(path.begin(), path.end());
        debug(path);
        int s = (int)path.size();
        bool ok = 1;
        bool anyway = 0;
        for (int i = 0; i<s; i++){
            int nxt = (i == s-1 ? -1 : path[i+1]);
            int v = path[i];
            for (auto x: g[v]){
                if (x == nxt || x == par[v]) continue;
                if (depth[v]%2 == 0){
                    if (dp[x][1] && ok){
                        anyway = 1;
                    }
                } else {
                    if (!dp[x][0]){
                        ok = 0;
                    }
                }
            }
        }
        debug(i, anyway, ok);
        for (int j = 1; j<=n; j++){
            //krawedz i--j
            // if (depth[i]%2 == 0){
                // if (win[1][0] || win[j][1]) {
                    // ans++;
                // }
            // } else {
                //gracz 2 moze podejmowac decyzje
                //nie dojdziemy w jakis sposob do wierzcholka i(?)
                //zeby dojsc do wierzcholka i, na calej sciezce od i do 1 gracz 2 musi wykonac decyzje, ze warto isc w te konkretne poddrzewo
                //dla gracza 1 moze sie oplacac tez skrecic gdzies indziej
                if (anyway || (ok && win[j][(depth[i]&1)^1])){
                    debug(i, j);
                    ans++;
                }
            // }
        }
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 21 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 27 ms 708 KB Output is correct
8 Correct 32 ms 736 KB Output is correct
9 Correct 21 ms 604 KB Output is correct
10 Correct 24 ms 860 KB Output is correct
11 Correct 23 ms 604 KB Output is correct

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 27 ms 708 KB Output is correct
8 Correct 32 ms 736 KB Output is correct
9 Correct 21 ms 604 KB Output is correct
10 Correct 24 ms 860 KB Output is correct
11 Correct 23 ms 604 KB Output is correct
12 Execution timed out 1046 ms 29748 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 27 ms 708 KB Output is correct
8 Correct 32 ms 736 KB Output is correct
9 Correct 21 ms 604 KB Output is correct
10 Correct 24 ms 860 KB Output is correct
11 Correct 23 ms 604 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Incorrect 21 ms 648 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 27 ms 708 KB Output is correct
8 Correct 32 ms 736 KB Output is correct
9 Correct 21 ms 604 KB Output is correct
10 Correct 24 ms 860 KB Output is correct
11 Correct 23 ms 604 KB Output is correct
12 Execution timed out 1046 ms 29748 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 21 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -