Submission #120828

#	Time	Username	Problem	Language	Result	Execution time	Memory
120828		IOrtroiii	Bridges (APIO19_bridges)	C++14	59 / 100	3045 ms	13876 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int N = 50500;
const int M = N + N;
const int Q = N + N;
const int MAGIC = 320;

struct Edge {
   int l, r;
   int from, to, lim;
   Edge(int l = 0, int r = 0, int from = 0, int to = 0, int lim = 0) :
      l(l), r(r), from(from), to(to), lim(lim) {}
   bool operator < (const Edge &e) const {
      return lim > e.lim;
   }
};

vector<Edge> es;

struct Query {
   int from, cost, id;
   Query(int from = 0, int cost = 0, int id = 0) :
      from(from), cost(cost), id(id) {}
   bool operator < (const Query &q) const {
      return cost > q.cost;
   }
};

vector<Query> qs;

int par[N];
int sz[N];

int find(int u) {
   if (par[u] != u) {
      par[u] = find(par[u]);
   }
   return par[u];
}

void merge(int u, int v) {
   u = find(u);
   v = find(v);
   if (u ^ v) {
      par[v] = u;
      sz[u] += sz[v];
   }
}

int from[M];
int to[M];
int lim[M];
int last[M];
int op[Q];
int ans[Q];
vector<int> g[N];
bool visit[N];

struct MyVector {
   int sz = 0;
   int a[N];
   bool has[N];
   void add(int u) {
      if (!has[u]) {
         has[u] = true;
         a[++sz] = u;
      }
   }
   void reset() {
      for (int i = 1; i <= sz; ++i) {
         int u = a[i];
         has[u] = false;
         g[u].clear();
         visit[u] = false;
      }
      sz = 0;
   }
} mv;

void dfs(int u, int &ans) {
   visit[u] = true;
   ans += sz[u];
   for (int v : g[u]) {
      if (!visit[v]) {
         dfs(v, ans);
      }
   }
}

int main() {
   int n, m;
   scanf("%d %d", &n, &m);
   for (int i = 1; i <= m; ++i) {
      scanf("%d %d %d", from + i, to + i, lim + i);
   }
   int q;
   scanf("%d", &q);
   for (int i = 1; i <= q; ++i) {
      scanf("%d", op + i);
      if (op[i] == 1) {
         int id, nlim;
         scanf("%d %d", &id, &nlim);
         es.emplace_back(last[id], i, from[id], to[id], lim[id]);
         lim[id] = nlim;
         last[id] = i;
      } else {
         int from, cost;
         scanf("%d %d", &from, &cost);
         qs.emplace_back(from, cost, i);
      }
   }
   for (int i = 1; i <= m; ++i) {
      if (last[i] != q) {
         es.emplace_back(last[i], q + 1, from[i], to[i], lim[i]);
      }
   }
   sort(es.begin(), es.end());
   sort(qs.begin(), qs.end());
   for (int l = 0; l < q + 1; l += MAGIC) {
      int r = min(l + MAGIC, q + 1);
      vector<Edge> all_es;
      vector<Edge> cand_es;
      for (auto e : es) {
         if (e.l <= l && r <= e.r) {
            all_es.push_back(e);
         } else if (e.l < r && l < e.r) {
            cand_es.push_back(e);
         }
      }
      vector<Query> cqs;
      for (auto qe : qs) {
         if (l <= qe.id && qe.id < r) {
            cqs.push_back(qe);
         }
      }
      for (int i = 1; i <= n; ++i) {
         par[i] = i;
         sz[i] = 1;
      }
      int ptr = 0;
      for (auto qe : cqs) {
         while (ptr < all_es.size() && all_es[ptr].lim >= qe.cost) {
            merge(all_es[ptr].from, all_es[ptr].to);
            ptr++;
         }
         mv.add(find(qe.from));
         for (auto e : cand_es) {
            if (e.lim >= qe.cost) {
               if (e.l <= qe.id && qe.id < e.r) {
                  int u = find(e.from);
                  int v = find(e.to);
                  mv.add(u);
                  mv.add(v);
                  g[u].push_back(v);
                  g[v].push_back(u);
               }
            } else {
               break;
            }
         }
         dfs(mv.a[1], ans[qe.id]);
         mv.reset();
      }
   }
   for (int i = 1; i <= q; ++i) if (op[i] == 2) {
      printf("%d\n", ans[i]);
   }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:144:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          while (ptr < all_es.size() && all_es[ptr].lim >= qe.cost) {
                 ~~~~^~~~~~~~~~~~~~~
bridges.cpp:94:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &m);
    ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:96:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", from + i, to + i, lim + i);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:99:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &q);
    ~~~~~^~~~~~~~~~
bridges.cpp:101:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", op + i);
       ~~~~~^~~~~~~~~~~~~~
bridges.cpp:104:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%d %d", &id, &nlim);
          ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:110:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%d %d", &from, &cost);
          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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