oj.uz

Submission #1117364

# Submission time Handle Problem Language Result Execution time Memory
1117364 2024-11-23T12:06:12 Z Zero_OP Capital City (JOI20_capital_city) C++14
0 / 100
 109 ms 48208 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int MAX = 2e5 + 5;

int N, K, timer_dfs, tin[MAX], tout[MAX], c[MAX], par[MAX];
vi adj[MAX], group[MAX], adj_color[MAX];

int low[MAX], num[MAX], cnt[MAX], bad[MAX], id[MAX], num_scc;
stack<int> st;



void dfs(int u, int p){
    tin[u] = ++timer_dfs;
    for(int v : adj[u]) if(v != p){
        par[v] = u;
        dfs(v, u);
    }
    tout[u] = timer_dfs;
}

void dfs_tarjan(int u){
    low[u] = num[u] = ++timer_dfs;
    st.push(u);

    for(int v : adj_color[u]){
        if(num[v]) minimize(low[u], num[v]);
        else{
            dfs_tarjan(v);
            minimize(low[u], low[v]);
        }
    }

    if(low[u] == num[u]){
        int v, sz = 0;
        ++num_scc;
        do{
            v = st.top(); st.pop();
            low[v] = num[v] = MAX;
            id[v] = num_scc;
            ++cnt[num_scc];
        } while(v != u);
    }
}

bool in_subtree(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

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

    file("task");

    cin >> N >> K;
    for(int i = 1; i < N; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    for(int i = 1; i <= N; ++i){
        cin >> c[i];
    }

    dfs(1, -1);

    for(int i = 1; i <= N; ++i){
        group[c[i]].emplace_back(tin[i]);
    }

    for(int i = 2; i <= N; ++i){
        int j = par[i];
        if(c[i] == c[j]) continue;

//        cout << "check ; " << j << ' ' << i << '\n';

        int p = lower_bound(all(group[c[j]]), tin[i]) - group[c[j]].begin();
        if(p < sz(group[c[j]]) && group[c[j]][p] <= tout[i]){
            adj_color[c[j]].emplace_back(c[i]); //c[j] need c[i]
        }

        if(!(in_subtree(i, group[c[i]].front()) && in_subtree(i, group[c[i]].back()))){
            adj_color[c[i]].emplace_back(c[j]); //c[i] need c[j]
        }
    }

    int ans = K;

    for(int i = 1; i <= K; ++i){
        if(!num[i]) dfs_tarjan(i);
    }

    for(int i = 1; i <= K; ++i){
        for(int j : adj_color[i]){
            if(id[i] != id[j]){
                bad[id[i]] = true;
            }
        }
    }

    for(int i = 1; i <= num_scc; ++i){
        if(!bad[i]) ans = min(ans, cnt[i] - 1);
    }

    cout << ans << '\n';

    return 0;
}

Compilation message

capital_city.cpp: In function 'void dfs_tarjan(int)':
capital_city.cpp:68:16: warning: unused variable 'sz' [-Wunused-variable]
   68 |         int v, sz = 0;
      |                ^~
capital_city.cpp: In function 'int main()':
capital_city.cpp:10:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:87:5: note: in expansion of macro 'file'
   87 |     file("task");
      |     ^~~~
capital_city.cpp:10:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:87:5: note: in expansion of macro 'file'
   87 |     file("task");
      |     ^~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 3 ms 20816 KB Output is correct
3 Correct 3 ms 20816 KB Output is correct
4 Correct 4 ms 18768 KB Output is correct
5 Incorrect 3 ms 16720 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 3 ms 20816 KB Output is correct
3 Correct 3 ms 20816 KB Output is correct
4 Correct 4 ms 18768 KB Output is correct
5 Incorrect 3 ms 16720 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 3 ms 20816 KB Output is correct
3 Correct 3 ms 20816 KB Output is correct
4 Correct 4 ms 18768 KB Output is correct
5 Incorrect 3 ms 16720 KB Output isn't correct
6 Halted 0 ms 0 KB -