Submission #120822

#	Time	Username	Problem	Language	Result	Execution time	Memory
120822		IOrtroiii	Bridges (APIO19_bridges)	C++14	73 / 100	3030 ms	12884 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 = 345;

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 pos[N];
int tt;

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 par2[N];
int sz2[N];

int find2(int u) {
   if (pos[u] != tt) {
      pos[u] = tt;
      par2[u] = par[u];
      sz2[u] = sz[u];
   }
   if (par2[u] != u) {
      par2[u] = find2(par2[u]);
   }
   return par2[u];
}

void merge2(int u, int v) {
   u = find2(u);
   v = find2(v);
   if (u ^ v) {
      par2[v] = u;
      sz2[u] += sz2[v];
   }
}

int from[M];
int to[M];
int lim[M];
int last[M];
int op[Q];
int ans[Q];

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++;
         }
         ++tt;
         for (auto e : cand_es) {
            if (e.l <= qe.id && qe.id < e.r && e.lim >= qe.cost) {
               merge2(e.from, e.to);
            }
         }
         ans[qe.id] = sz2[find2(qe.from)];
      }
   }
   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:137:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          while (ptr < all_es.size() && all_es[ptr].lim >= qe.cost) {
                 ~~~~^~~~~~~~~~~~~~~
bridges.cpp:87: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:89: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:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &q);
    ~~~~~^~~~~~~~~~
bridges.cpp:94:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", op + i);
       ~~~~~^~~~~~~~~~~~~~
bridges.cpp:97: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:103: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: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27