Submission #1254592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254592		thdh__	Mergers (JOI19_mergers)	C++20	100 / 100	185 ms	51760 KiB

mergers

#pragma GCC optimize ("O3, unroll-loops")
#include <bits/stdc++.h>

#define pii pair <int, int>
#define fi first
#define se second

using namespace std;

const int maxN = 5e5 + 5;

int S[maxN], par[maxN], sz[maxN];
vector <int> adj[maxN];
int last[maxN];
int cnt[maxN];
int up[maxN], depth[maxN];

const int BUFFER_SIZE = 1 << 20;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;

inline char nextChar() {
    if (input_pos == input_len) {
        input_pos = 0;
        input_len = fread(input_buffer, 1, BUFFER_SIZE, stdin);
        if (input_len == 0) return EOF;
    }
    return input_buffer[input_pos++];
}

inline void fast_read(int &x) {
    x = 0;
    char c;
    bool neg = false;
    do {
        c = nextChar();
    } while (c != '-' && (c < '0' || c > '9'));

    if (c == '-') {
        neg = true;
        c = nextChar();
    }

    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = nextChar();
    }

    if (neg) x = -x;
}

inline void init (int n) {
    for (int i = 1; i <= n; i ++) {
        par[i] = i;
        sz[i] = 1;
    }
}

int getRoot (int u) {
    if (par[u] == u) {
        return u;
    }
    return (par[u] = getRoot (par[u]));
}

inline void join (int u, int v) {
    u = getRoot (u);
    v = getRoot (v);
    if (u == v) {
        return;
    }
    if (depth[u] > depth[v]) {
        swap (u, v);
    }
    par[v] = u;
    sz[u] += sz[v];
    return;
}

inline void merge (int u, int v) {
    while (u != v) {
        //cout << u << ' ' << v << '\n';
        if (depth[u] < depth[v]) {
            swap (u, v);
        }
        join (u, up[u]);
        u = getRoot (u);
    }
}

void dfs (int u, int p) {
    up[u] = p;
    for (auto v : adj[u]) {
        if (v == p) {
            continue;
        }
        depth[v] = depth[u] + 1;
        dfs (v, u);
    }
}

int main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    int n, k;
    fast_read (n);
    fast_read (k);
    init (n);
    for (int i = 1; i < n; i ++) {
        int u, v;
        fast_read (u);
        fast_read (v);
        adj[u].push_back (v);
        adj[v].push_back (u);
    }
    dfs (1, 0);
    for (int i = 1; i <= n; i ++) {
        fast_read (S[i]);
        if (last[S[i]] != 0) {
            merge (i, last[S[i]]);
        }
        last[S[i]] = i;
    }
    for (int u = 1; u <= n; u ++) {
        for (auto v : adj[u]) {
            int i = getRoot (u);
            int j = getRoot (v);
            if (i != j) {
                cnt[i] ++;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++) {
        res += (cnt[i] == 1);
    }
    cout << (res + 1) / 2;
    return 0;
}

Compilation message (stderr)

mergers.cpp:1:41: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize ("O3, unroll-loops")
      |                                         ^
mergers.cpp:22:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   22 | inline char nextChar() {
      |                      ^
mergers.cpp:31:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   31 | inline void fast_read(int &x) {
      |                             ^
mergers.cpp:52:24: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   52 | inline void init (int n) {
      |                        ^
mergers.cpp:59:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   59 | int getRoot (int u) {
      |                   ^
mergers.cpp:66:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   66 | inline void join (int u, int v) {
      |                               ^
mergers.cpp:80:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   80 | inline void merge (int u, int v) {
      |                                ^
mergers.cpp:91:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   91 | void dfs (int u, int p) {
      |                       ^
mergers.cpp:102:11: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  102 | int main () {
      |           ^

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