제출 #711803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711803		lukameladze	Mergers (JOI19_mergers)	C++14	100 / 100	1259 ms	135944 KiB

mergers

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5e5 + 5;
int t,n,a[N],sz[N],tin,in[N],out[N],p[N],par[N][20],k,x[N],lv[N],deg[N];
vector <int> v[N];
vector <pii> vec[N];
void dfs(int a, int p) {
    tin++;
    in[a] = tin;
    par[a][0] = p;
    for (int i = 1; i <= 18; i++) {
        if (par[a][i - 1]) par[a][i] = par[par[a][i - 1]][i - 1];
    }
    lv[a] = lv[p] + 1;
    for (int to : v[a]) {
        if (to == p) continue;
        dfs(to, a);
    }
    out[a] = tin;
}
void init() {
    for (int i = 1; i <= n; i++) {
        p[i] = i; sz[i] = 1;
    }
}
int get_col(int a) {
    if (a == p[a]) return a;
    else return p[a] = get_col(p[a]); 
}
void col(int a, int b) {
    a = get_col(a); b = get_col(b);
    if (a == b) return ;
    if (lv[a] > lv[b]) swap(a, b);
    p[b] = a;
}
void merge(int a, int lc) {
    while (get_col(a) != get_col(lc)) {
        col(a, par[get_col(a)][0]);
    }
}
int upper(int a, int b) {
    return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
    if (upper(a, b)) return a;
    for (int i = 18; i >= 0; i--) {
        if (par[a][i] && !upper(par[a][i], b)) a = par[a][i];
    }
    return par[a][0];
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    vector <pii> edges;
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
        edges.pb({a,b});
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        cin>>x[i];
    }
    init();
    for (int i = 1; i <= n; i++) {
        vec[x[i]].pb({in[i], i});
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < vec[i].size(); j++) {
            int a = vec[i][j].s, b = vec[i][(j + 1) % vec[i].size()].s, lc = lca(a, b);
            merge(a, lc); merge(b, lc);
        }
    }
    for (pii sth : edges) {
        if (get_col(sth.f) != get_col(sth.s)) {
            deg[get_col(sth.f)]++; deg[get_col(sth.s)]++;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += (int)(deg[i] == 1);
    }
    cout<<(cnt + 1) / 2<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main() {
      | ^~~~
mergers.cpp: In function 'int main()':
mergers.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int j = 0; j < vec[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30