oj.uz

Submission #216824

# Submission time Handle Problem Language Result Execution time Memory
216824 2020-03-28T06:36:31 Z IOrtroiii Capital City (JOI20_capital_city) C++14
1 / 100
 3000 ms 36076 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200200;

int N, K;
vector<int> adj[MAXN];
int city[MAXN];
int par[MAXN];
vector<int> towns[MAXN];
int sz[MAXN];
bool delt[MAXN];
vector<int> curComp;
int ans = MAXN;

void dfsSz(int v, int p) {
   sz[v] = 1;
   for (int u : adj[v]) if (u != p && !delt[u]) {
      dfsSz(u, v);
      sz[v] += sz[u];
   }
}

int findCentr(int v, int p, int r) {
   for (int u : adj[v]) if (u != p && !delt[u] && 2 * sz[u] >= sz[r]) {
      return findCentr(u, v, r);
   }
   return v;
}

int dfsPar(int v, int p) {
   par[v] = p;
   curComp.emplace_back(v);
   for (int u : adj[v]) if (u != p && !delt[u]) {
      dfsPar(u, v);
   }
}

int root[MAXN];

int getRoot(int v) {
   if (root[v] != v) {
      root[v] = getRoot(root[v]);
   }
   return root[v];
}

bool merge(int v, int u) {
   v = getRoot(v);
   u = getRoot(u);
   if (v == u) {
      return false;
   } else {
      root[u] = v;
      return true;
   }
}

int cnt[MAXN];

void solve(int v) {
   dfsSz(v, v);
   v = findCentr(v, v, v);
   dfsPar(v, v);
   for (int u : curComp) {
      ++cnt[city[u]];
   }
   bool good = cnt[city[v]] == int(towns[city[v]].size());
   int cans = 0;
   queue<int> q;
   for (int u : towns[city[v]]) {
      q.emplace(u);
   }
   while (!q.empty()) {
      int u = q.front(); q.pop();
      if (merge(city[u], city[par[u]])) {
         good &= (cnt[city[par[u]]] == int(towns[city[par[u]]].size()));
         if (!good) break;
         cans++;
         for (int z : towns[city[par[u]]]) {
            q.emplace(z);
         }
      }
   }
   if (good) ans = min(ans, cans);
   for (int z : curComp) {
      root[city[z]] = city[z];
      cnt[city[z]] = 0;
   }
   curComp = {};
   delt[v] = true;
   for (int u : adj[v]) if (!delt[u]) solve(u);
}

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   cin >> N >> K;
   for (int i = 1; i < N; ++i) {
      int v, u;
      cin >> v >> u;
      adj[v].emplace_back(u);
      adj[u].emplace_back(v);
   }
   for (int v = 1; v <= N; ++v) {
      cin >> city[v];
      towns[city[v]].emplace_back(v);
   }
   iota(root + 1, root + K + 1, 1);
   solve(1);
   cout << ans << "\n";
   return 0;
}

Compilation message

capital_city.cpp: In function 'int dfsPar(int, int)':
capital_city.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9856 KB Output is correct
2 Correct 10 ms 9856 KB Output is correct
3 Correct 9 ms 9856 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9856 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 11 ms 9856 KB Output is correct
12 Correct 12 ms 9984 KB Output is correct
13 Correct 12 ms 9856 KB Output is correct
14 Correct 11 ms 9856 KB Output is correct
15 Correct 11 ms 9984 KB Output is correct
16 Correct 11 ms 9984 KB Output is correct
17 Correct 20 ms 9984 KB Output is correct
18 Correct 22 ms 9984 KB Output is correct
19 Correct 19 ms 9984 KB Output is correct
20 Correct 20 ms 9984 KB Output is correct
21 Correct 20 ms 9984 KB Output is correct
22 Correct 12 ms 9984 KB Output is correct
23 Incorrect 12 ms 9984 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 35700 KB Output is correct
2 Correct 277 ms 35948 KB Output is correct
3 Correct 651 ms 35432 KB Output is correct
4 Correct 279 ms 36076 KB Output is correct
5 Correct 2959 ms 33004 KB Output is correct
6 Correct 344 ms 35824 KB Output is correct
7 Execution timed out 3088 ms 33132 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9856 KB Output is correct
2 Correct 10 ms 9856 KB Output is correct
3 Correct 9 ms 9856 KB Output is correct
4 Correct 10 ms 9856 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9856 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 11 ms 9856 KB Output is correct
12 Correct 12 ms 9984 KB Output is correct
13 Correct 12 ms 9856 KB Output is correct
14 Correct 11 ms 9856 KB Output is correct
15 Correct 11 ms 9984 KB Output is correct
16 Correct 11 ms 9984 KB Output is correct
17 Correct 20 ms 9984 KB Output is correct
18 Correct 22 ms 9984 KB Output is correct
19 Correct 19 ms 9984 KB Output is correct
20 Correct 20 ms 9984 KB Output is correct
21 Correct 20 ms 9984 KB Output is correct
22 Correct 12 ms 9984 KB Output is correct
23 Incorrect 12 ms 9984 KB Output isn't correct
24 Halted 0 ms 0 KB -