oj.uz

Submission #931649

# Submission time Handle Problem Language Result Execution time Memory
931649 2024-02-22T07:53:49 Z vjudge1 Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 184684 KB 
/// ITNOG
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define FOR(i,k,n) for(int i = k; i < n; ++ i)
#define debf cout<<"(0-0)\n";
#define all(x) x.begin(), x.end()
#define dec(x) cout << fixed << setprecision(x);
#define pf push_front
#define ppf pop_front
#define dash " ------- "
#define what(x) cerr << #x << " is " << x << endl;
#define eb emplace_back
//#define int short int
#define int long long
#define sz(s) (int) (s.size())
#define fl cout.flush()

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef long double ld;

template <class T> using max_heap = priority_queue <T, vector <T>, less <T> >;
template <class T> using min_heap = priority_queue <T, vector <T>, greater <T> >;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr int MOD = 1e9 + 7, N = 2e5 + 8, M = 1e6, SQ = 600, INF = 1e15 + 8, LGN = 22, mod = 998244353, P = 131113;

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

bool mark[N];
int n, k, col[N], st[N], xxx, sz;
vector <int> adj[N];
vector <int> v[N];

bool dfs (int u, int par = -1){
  bool ok = false;
  if (col[u] == xxx){
    ok = true;
  }
  for (int i : adj[u]){
    if (i != par){
      ok |= dfs (i, u);
    }
  }
  if (ok){
    if (col[u] != xxx){
      v[xxx].pb(col[u]);
    }
  }
  return ok;
}

void dfs2 (int u){
  mark[u] = true;
  //cout << xxx + 1 << " " << u + 1 << '\n';
  ++ sz;
  for (int i : v[u]){
    if (!mark[i]){
      dfs2 (i);
    }
  }
  return;
}

int32_t main(){
  fast_io;
  cin >> n >> k;
  FOR (i, 0, n - 1){
    int aa, bb;
    cin >> aa >> bb;
    adj[--aa].pb(--bb);
    adj[bb].pb(aa);
  }
  FOR (i, 0, n){
    cin >> col[i];
    st[--col[i]] = i;
  }
  for (int i = 0; i < k; ++ i){
    xxx = i;
    dfs (st[i]);
    sort (all(v[xxx]));
    v[xxx].resize(unique(all(v[xxx])) - v[xxx].begin());
  }
  //cout << "--- " << v[2].size() << " " << v[2].back() + 1 << '\n';
  int ans = 0;
  ans = 1000000;
  for (int i = 0; i < k; ++ i){
    fill (mark, mark + 2008, false);
    sz = 0;
    xxx = i;
    dfs2 (i);
    ans = min (ans, sz - 1);
  }
  cout << ans;
  return 0;
}

// Yesterday is history
// Tomorrow is a mystery
// but today is a gift
// That is why it is called the present

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 9 ms 12892 KB Output is correct
12 Correct 10 ms 13144 KB Output is correct
13 Correct 9 ms 12892 KB Output is correct
14 Correct 9 ms 12892 KB Output is correct
15 Correct 18 ms 13404 KB Output is correct
16 Correct 20 ms 14072 KB Output is correct
17 Correct 12 ms 14940 KB Output is correct
18 Correct 13 ms 14940 KB Output is correct
19 Correct 13 ms 15232 KB Output is correct
20 Correct 13 ms 15096 KB Output is correct
21 Correct 13 ms 14936 KB Output is correct
22 Correct 139 ms 23120 KB Output is correct
23 Correct 140 ms 22608 KB Output is correct
24 Correct 17 ms 12888 KB Output is correct
25 Correct 16 ms 13144 KB Output is correct
26 Correct 14 ms 13148 KB Output is correct
27 Correct 15 ms 13256 KB Output is correct
28 Correct 13 ms 13404 KB Output is correct
29 Correct 14 ms 13660 KB Output is correct
30 Correct 13 ms 13404 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 2 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 9 ms 12892 KB Output is correct
12 Correct 10 ms 13144 KB Output is correct
13 Correct 9 ms 12892 KB Output is correct
14 Correct 9 ms 12892 KB Output is correct
15 Correct 18 ms 13404 KB Output is correct
16 Correct 20 ms 14072 KB Output is correct
17 Correct 12 ms 14940 KB Output is correct
18 Correct 13 ms 14940 KB Output is correct
19 Correct 13 ms 15232 KB Output is correct
20 Correct 13 ms 15096 KB Output is correct
21 Correct 13 ms 14936 KB Output is correct
22 Correct 139 ms 23120 KB Output is correct
23 Correct 140 ms 22608 KB Output is correct
24 Correct 17 ms 12888 KB Output is correct
25 Correct 16 ms 13144 KB Output is correct
26 Correct 14 ms 13148 KB Output is correct
27 Correct 15 ms 13256 KB Output is correct
28 Correct 13 ms 13404 KB Output is correct
29 Correct 14 ms 13660 KB Output is correct
30 Correct 13 ms 13404 KB Output is correct
31 Execution timed out 3045 ms 184684 KB Time limit exceeded
32 Halted 0 ms 0 KB -