oj.uz

Submission #248662

# Submission time Handle Problem Language Result Execution time Memory
248662 2020-07-13T01:50:47 Z fivefourthreeone Mergers (JOI19_mergers) C++17
0 / 100
 128 ms 39920 KB 
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 998244353;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 500001;
vector<int> adj[mxN];
int n, k;
vector<int> state[mxN];
int high[mxN];
int depth[mxN];
int val[mxN];
int par[mxN][21];
bool flag[mxN];
int best[mxN];
int ans = 0;
int walk(int a, int b) {
    uwu(lg, 21, 0) {
        if(b&(1<<lg)) {
            a = par[a][lg];
        }
    }
    return a;
}
int lca(int a, int b) {
    if(depth[a]<depth[b]) {
        walk(b, depth[b]-depth[a]);
    }else if(depth[a]>depth[b]) {
        walk(a, depth[a]-depth[b]);
    }
    if(a==b)return a;
    uwu(lg, 21, 0) {
        if(par[a][lg]!=par[b][lg]) {
            a = par[a][lg];
            b = par[b][lg];
        }
    }
    return par[a][0];
}
void dfs(int u, int p) {
    par[u][0] = p;
    for(int v: adj[u]) {
        if(v==p)continue;
        depth[v] =depth[u]+1;
        dfs(v, u);
    }
}
void solve(int u, int p) {
    best[u] = depth[high[val[u]]];
    for(int v: adj[u]) {
        if(v==p)continue;
        solve(v, u);
        if(flag[v]) {
            flag[u] = true;
            return;
        }
        best[u] = min(best[u], best[v]);
    }
    //cout<<u<<" "<<best[u]<<"\n";
    if(depth[best[u]]==depth[u]&&u!=p) {
        ans++;
        flag[u] = true;
    }
}
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>k;
    int a, b;
    owo(i, 0, n-1) {
        cin>>a>>b;
        a--; b--;
        adj[a].senpai(b);
        adj[b].senpai(a);
    }
    owo(i, 0, n) {
        cin>>a;
        a--;
        val[i] = a;
        state[a].senpai(i);
    }
    dfs(0, 0);
    owo(lg, 1, 21){
        owo(i, 0, n) {
            par[i][lg] = par[par[i][lg-1]][lg-1];
        }
    }
    owo(i, 0, k) {
        int comlca = state[i][0];
        owo(j, 1, state[i].size()) {
            comlca = lca(comlca, state[i][j]);
        }
        high[i] = comlca;
        //cout<<i<<" "<<high[i]<<"\n";
    }
    solve(0, 0);
    cout<<((ans+1)/2)<<"\n";
    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:2:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define owo(i,a, b) for(int i=(a); i<(b); ++i)
                                     ^
mergers.cpp:104:9: note: in expansion of macro 'owo'
         owo(j, 1, state[i].size()) {
         ^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 37232 KB Output is correct
2 Incorrect 89 ms 39920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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