Submission #110825

#	Time	Username	Problem	Language	Result	Execution time	Memory
110825		IOrtroiii	Mergers (JOI19_mergers)	C++14	100 / 100	1137 ms	69624 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int N = 500500;

int n, m;
int a[N];
pair<int, int> e[N];
vector< pair<int, int> > g[N];
bool br[N];
int num[N], low[N], tt;

void dfs(int u,int p) {
   num[u] = low[u] = ++tt;
   for (auto nx : g[u]) {
      int v, id; tie(v, id) = nx;
      if (!num[v]) {
         dfs(v, id);
         low[u] = min(low[u], low[v]);
         if (low[v] > num[u]) br[id] = true;
      } else if (id != p) low[u] = min(low[u], num[v]);
   }
}

int cnt;
int comp[N];
int deg[N];

void dfs2(int u) {
   comp[u] = cnt;
   for (auto nx : g[u]) {
      int v, id; tie(v, id) = nx;
      if (!br[id] && !comp[v]) {
         dfs2(v);
      }
   }
}

int main() {
   scanf("%d %d", &n, &m);
   for (int i = 1; i < n; ++i) {
      int u, v; scanf("%d %d", &u, &v);
      e[i] = {u, v};
   }
   for (int i = 1; i <= n; ++i) scanf("%d", a + i);
   for (int i = 1; i < n; ++i) {
      int u, v; tie(u, v) = e[i];
      u = a[u], v = a[v];
      if (u == v) continue;
      g[u].push_back({v, i});
      g[v].push_back({u, i});
   }

   dfs(1, -1);
   for (int i = 1; i <= m; ++i) {
      if (!comp[i]) {
         ++cnt;
         dfs2(i);
      }
   }
   for (int i = 1; i <= n; ++i) {
      for (auto nx : g[i]) {
         int v, id; tie(v, id) = nx;
         if (br[id]) ++deg[comp[v]];
      }
   }
   printf("%d\n", (count(deg + 1, deg + cnt + 1, 1) + 1) / 2);
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:68:61: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::iterator_traits<int*>::difference_type {aka long int}' [-Wformat=]
    printf("%d\n", (count(deg + 1, deg + cnt + 1, 1) + 1) / 2);
                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
mergers.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &m);
    ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:43:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int u, v; scanf("%d %d", &u, &v);
                 ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:46:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
                                 ~~~~~^~~~~~~~~~~~~

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