oj.uz

Submission #889892

# Submission time Handle Problem Language Result Execution time Memory
889892 2023-12-20T09:13:59 Z hafo Unique Cities (JOI19_ho_t5) C++14
0 / 100
 2000 ms 17804 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, dp[maxn][2], a[maxn], u, v, m, mx[3][maxn][2], res[maxn];
vector<int> g[maxn];

struct sub3 {
    void dfs(int u, int par) {
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 3; j++) mx[j][u][i] = 0;
        }
        for(auto v:g[u]) {
            if(v == par) continue;
            dfs(v, u);
            for(int i = 0; i < 2; i++) {
                for(int j = 0; j < 3; j++) {
                    if(mx[j][u][i] < dp[v][i]) {
                        for(int k = 2; k > j; k--) mx[k][u][i] = mx[k - 1][u][i];
                        mx[j][u][i] = dp[v][i];
                        break;
                    }
                }
            }
        }

        dp[u][0] = min(mx[0][u][0] - mx[1][u][0], mx[0][u][1] - mx[1][u][1]) + 1;
        dp[u][1] = mx[0][u][1] + 1;
    }

    void dfs2(int u, int par) {
        res[u] = dp[u][0] - 1;
        for(auto v:g[u]) {
            if(v == par) continue;

            int tmp_mx[3][2][2], tmp_dp[2][2];
            for(int i = 0; i < 2; i++) {
                for(int j = 0; j < 3; j++) tmp_mx[j][0][i] = mx[j][u][i];
                for(int j = 0; j < 3; j++) {
                    if(mx[j][u][i] == dp[v][i]) {
                        for(int k = j; k < 3; k++) mx[k][u][i] = mx[k + 1][u][i];
                        break;
                    }
                }
            }   

            for(int i = 0; i < 2; i++) tmp_dp[0][i] = dp[u][i];
            dp[u][0] = min(mx[0][u][0] - mx[1][u][0], mx[0][u][1] - mx[1][u][1]) + 1;
            dp[u][1] = mx[0][u][1] + 1;

            for(int i = 0; i < 2; i++) {
                for(int j = 0; j < 3; j++) tmp_mx[j][1][i] = mx[j][v][i];

                for(int j = 0; j < 3; j++) {
                    if(mx[j][v][i] < dp[u][i]) {
                        for(int k = 2; k > j; k--) mx[k][v][i] = mx[k - 1][v][i];
                        mx[j][v][i] = dp[u][i];
                        break;
                    }
                }
            }

            for(int i = 0; i < 2; i++) tmp_dp[1][i] = dp[v][i];
            dp[v][0] = min(mx[0][v][0] - mx[1][v][0], mx[0][v][1] - mx[1][v][1]) + 1;
            dp[v][1] = mx[0][v][1] + 1;
            dfs2(v, u);

            for(int i = 0; i < 2; i++) {
                for(int j = 0; j < 3; j++) {
                    mx[j][u][i] = tmp_mx[j][0][i];
                    mx[j][v][i] = tmp_mx[j][1][i];
                }
            }
            for(int i = 0; i < 2; i++) {
                dp[u][i] = tmp_dp[0][i];
                dp[v][i] = tmp_dp[1][i];
            }
        }
    }

    void solve() {
        // dfs(1, 0);
        // dfs2(1, 0);
        // for(int i = 1; i <= n; i++) {
        //     if(m == 1) cout<<(res[i] > 0)<<"\n";
        //     else cout<<res[i]<<"\n";
        // }

        for(int i = 1; i <= n; i++) {
            dfs(i, 0);
            cout<<dp[i][0] - 1<<"\n";
        }
    }
} sub3;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m;
    for(int i = 1; i < n; i++) {
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }

    for(int i = 1; i <= n; i++) cin>>a[i];

    sub3.solve();
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Incorrect 80 ms 12888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2017 ms 16528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 17804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Incorrect 80 ms 12888 KB Output isn't correct
3 Halted 0 ms 0 KB -