제출 #187240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
187240		MiricaMatei	다리 (APIO19_bridges)	C++14	0 / 100	477 ms	12520 KiB

bridges

///brut

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
const int MAXM = 100005;
const int MAXQ = 100005;
const int INF = 1000000000;

struct Edge {
  int u, v, c;
  bool operator < (const Edge& other) const {
    return c > other.c;
  }
  int other(int node) {
    return u ^ v ^ node;
  }
}e[MAXM];

vector<int>G[MAXN];
int aint[4 * MAXN];

void build(int node, int l, int r) {
  aint[node] = INF;
  if (l == r)
    return ;
  int mid = (l + r) / 2;
  build(2 * node, l, mid);
  build(2 * node + 1, mid + 1, r);
}

void update(int node, int l, int r, int pos, int val) {
  if (l == r) {
    aint[node] = val;
    return ;
  }
  int mid = (l + r) / 2;
  if (pos <= mid)
    update(2 * node, l, mid, pos, val);
  else
    update(2 * node + 1, mid + 1, r, pos, val);
  aint[node] = min(aint[2 * node], aint[2 * node + 1]);
}

int query(int node, int l, int r, int a, int b) {
  if (a <= l && r <= b)
    return aint[node];
  int mid = (l + r) / 2;
  int ans = INF;
  if (a <= mid)
    ans = query(2 * node, l, mid, a, b);
  if (b > mid)
    ans = min(ans, query(2 * node + 1, mid + 1, r, a, b));
  return ans;
}

struct Node {
  int u, val;
  bool operator < (const Node& other) const {
    return val < other.val;
  }
};

bool vis[MAXN];

struct Query {
  int node, val, w;
  bool operator < (const Query& other) const {
    return val > other.val;
  }
}v[MAXQ];

int t[MAXN], h[MAXN], sz[MAXN];
int ans[MAXQ];

int f(int a) {
  if (a == t[a])
    return a;
  return f(t[a]);
}

void u(int a, int b) {
  a = f(a);
  b = f(b);
  if (a == b)
    return ;
  if (h[a] < h[b])
    swap(a, b);
  sz[a] += sz[b];
  t[b] = a;
  if (h[a] == h[b])
    h[a]++;
}

int main() {

  int n, m, q;
  scanf("%d%d", &n, &m);
  bool ok = (m == n - 1);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
    G[e[i].u].push_back(i);
    G[e[i].v].push_back(i);
    if (e[i].u != i || e[i].v != i + 1)
      ok = 0;
  }
  scanf("%d", &q);
  if (ok == 1) {
    build(1, 1, n - 1);
    for (int i = 1; i < n; ++i)
      update(1, 1, n - 1, i, e[i].c);
    for (int i = 1; i <= q; ++i) {
      int t, a, b;
      scanf("%d%d%d", &t, &a, &b);
      if (t == 1) {
        update(1, 1, n - 1, a, b);
      } else {
        int ans = 1;
        int l = 1, r = a - 1, last = a;
        while (l <= r) {
          int mid = (l + r) / 2;
          if (query(1, 1, n - 1, mid, a - 1) >= b) {
            last = mid;
            r = mid - 1;
          } else {
            l = mid + 1;
          }
        }
        ans += a - last;
        l = a;
        r = n - 1;
        last = a - 1;
        while (l <= r) {
          int mid = (l + r) / 2;
          if (query(1, 1, n - 1, a, mid) >= b) {
            last = mid;
            l = mid + 1;
          } else {
            r = mid - 1;
          }
        }
        ans += last - a + 1;
        printf("%d\n", ans);
      }
    }
  } else if (n <= 1000 && m <= 1000 && q <= 10000) {
    for (int i = 1; i <= q; ++i) {
      int t, a, b;
      scanf("%d%d%d", &t, &a, &b);
      if (t == 1) {
        e[a].c = b;
      } else {
        memset(vis, 0, sizeof(vis));
        priority_queue<Node>pq;
        pq.push({a, INF});
        int ans = 0;
        while (!pq.empty()) {
          Node aux = pq.top();
          pq.pop();
          if (vis[aux.u])
            continue;
          vis[aux.u] = 1;
          ans++;
          for (auto it:G[aux.u]) {
            int u = e[it].other(aux.u);
            if (!vis[u] && min(aux.val, e[it].c) >= b)
              pq.push({u, min(aux.val, e[it].c)});
          }
        }
        printf("%d\n", ans);
      }
    }
  } else {
    for (int i = 1; i <= q; ++i) {
      int t;
      scanf("%d%d%d", &t, &v[i].node, &v[i].val);
      v[i].w = i;
    }
    sort(v + 1, v + q + 1);
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= n; ++i) {
      t[i] = i;
      h[i] = 1;
      sz[i] = 1;
    }
    for (int i = 1, j = 1; i <= q || j <= m;) {
      if (i <= q && (j > m || v[i].val > e[i].c)) {
        ans[v[i].w] = sz[f(v[i].node)];
        i++;
      } else {
        u(e[j].u, e[j].v);
        j++;
      }
    }
    for (int i = 1; i <= q; ++i)
      printf("%d\n", ans[i]);
  }

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
bridges.cpp:116:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d", &t, &a, &b);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:151:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d", &t, &a, &b);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:178:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d", &t, &v[i].node, &v[i].val);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27