Submission #120830

# Submission time Handle Problem Language Result Execution time Memory
120830 2019-06-25T15:03:45 Z IOrtroiii Bridges (APIO19_bridges) C++14
100 / 100
1749 ms 31868 KB
#include <bits/stdc++.h>

using namespace std;

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

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

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);
          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1536 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 24 ms 2048 KB Output is correct
4 Correct 8 ms 1856 KB Output is correct
5 Correct 17 ms 1920 KB Output is correct
6 Correct 13 ms 1920 KB Output is correct
7 Correct 17 ms 1920 KB Output is correct
8 Correct 18 ms 1920 KB Output is correct
9 Correct 22 ms 1920 KB Output is correct
10 Correct 18 ms 1920 KB Output is correct
11 Correct 17 ms 1920 KB Output is correct
12 Correct 20 ms 1920 KB Output is correct
13 Correct 23 ms 2040 KB Output is correct
14 Correct 20 ms 2048 KB Output is correct
15 Correct 20 ms 2048 KB Output is correct
16 Correct 17 ms 2032 KB Output is correct
17 Correct 17 ms 2048 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 943 ms 9928 KB Output is correct
2 Correct 1024 ms 10036 KB Output is correct
3 Correct 980 ms 9984 KB Output is correct
4 Correct 910 ms 10000 KB Output is correct
5 Correct 950 ms 9876 KB Output is correct
6 Correct 1536 ms 9628 KB Output is correct
7 Correct 1409 ms 9748 KB Output is correct
8 Correct 1351 ms 9720 KB Output is correct
9 Correct 94 ms 3820 KB Output is correct
10 Correct 1162 ms 9896 KB Output is correct
11 Correct 1036 ms 10028 KB Output is correct
12 Correct 632 ms 8540 KB Output is correct
13 Correct 757 ms 10452 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 726 ms 7852 KB Output is correct
2 Correct 571 ms 5032 KB Output is correct
3 Correct 803 ms 7808 KB Output is correct
4 Correct 803 ms 7808 KB Output is correct
5 Correct 91 ms 3816 KB Output is correct
6 Correct 754 ms 7828 KB Output is correct
7 Correct 605 ms 7700 KB Output is correct
8 Correct 512 ms 7736 KB Output is correct
9 Correct 342 ms 7156 KB Output is correct
10 Correct 311 ms 6932 KB Output is correct
11 Correct 487 ms 8136 KB Output is correct
12 Correct 450 ms 8048 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1198 ms 11848 KB Output is correct
2 Correct 90 ms 3816 KB Output is correct
3 Correct 96 ms 9504 KB Output is correct
4 Correct 87 ms 9524 KB Output is correct
5 Correct 1157 ms 12000 KB Output is correct
6 Correct 1210 ms 11996 KB Output is correct
7 Correct 1218 ms 12020 KB Output is correct
8 Correct 479 ms 7964 KB Output is correct
9 Correct 463 ms 7976 KB Output is correct
10 Correct 450 ms 8028 KB Output is correct
11 Correct 869 ms 10472 KB Output is correct
12 Correct 792 ms 10812 KB Output is correct
13 Correct 814 ms 10756 KB Output is correct
14 Correct 1257 ms 11912 KB Output is correct
15 Correct 1100 ms 11956 KB Output is correct
16 Correct 1161 ms 11888 KB Output is correct
17 Correct 1163 ms 12056 KB Output is correct
18 Correct 1158 ms 11924 KB Output is correct
19 Correct 1164 ms 11816 KB Output is correct
20 Correct 984 ms 11172 KB Output is correct
21 Correct 912 ms 11176 KB Output is correct
22 Correct 1181 ms 11676 KB Output is correct
23 Correct 940 ms 10824 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 943 ms 9928 KB Output is correct
2 Correct 1024 ms 10036 KB Output is correct
3 Correct 980 ms 9984 KB Output is correct
4 Correct 910 ms 10000 KB Output is correct
5 Correct 950 ms 9876 KB Output is correct
6 Correct 1536 ms 9628 KB Output is correct
7 Correct 1409 ms 9748 KB Output is correct
8 Correct 1351 ms 9720 KB Output is correct
9 Correct 94 ms 3820 KB Output is correct
10 Correct 1162 ms 9896 KB Output is correct
11 Correct 1036 ms 10028 KB Output is correct
12 Correct 632 ms 8540 KB Output is correct
13 Correct 757 ms 10452 KB Output is correct
14 Correct 726 ms 7852 KB Output is correct
15 Correct 571 ms 5032 KB Output is correct
16 Correct 803 ms 7808 KB Output is correct
17 Correct 803 ms 7808 KB Output is correct
18 Correct 91 ms 3816 KB Output is correct
19 Correct 754 ms 7828 KB Output is correct
20 Correct 605 ms 7700 KB Output is correct
21 Correct 512 ms 7736 KB Output is correct
22 Correct 342 ms 7156 KB Output is correct
23 Correct 311 ms 6932 KB Output is correct
24 Correct 487 ms 8136 KB Output is correct
25 Correct 450 ms 8048 KB Output is correct
26 Correct 987 ms 9876 KB Output is correct
27 Correct 1476 ms 13032 KB Output is correct
28 Correct 1448 ms 18608 KB Output is correct
29 Correct 976 ms 12952 KB Output is correct
30 Correct 1543 ms 9928 KB Output is correct
31 Correct 1541 ms 10156 KB Output is correct
32 Correct 1481 ms 9904 KB Output is correct
33 Correct 1202 ms 10112 KB Output is correct
34 Correct 1284 ms 9968 KB Output is correct
35 Correct 1323 ms 10012 KB Output is correct
36 Correct 930 ms 10072 KB Output is correct
37 Correct 913 ms 9956 KB Output is correct
38 Correct 894 ms 10008 KB Output is correct
39 Correct 617 ms 9016 KB Output is correct
40 Correct 655 ms 9040 KB Output is correct
41 Correct 649 ms 9068 KB Output is correct
42 Correct 616 ms 10548 KB Output is correct
43 Correct 638 ms 10600 KB Output is correct
44 Correct 626 ms 10564 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1536 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 24 ms 2048 KB Output is correct
4 Correct 8 ms 1856 KB Output is correct
5 Correct 17 ms 1920 KB Output is correct
6 Correct 13 ms 1920 KB Output is correct
7 Correct 17 ms 1920 KB Output is correct
8 Correct 18 ms 1920 KB Output is correct
9 Correct 22 ms 1920 KB Output is correct
10 Correct 18 ms 1920 KB Output is correct
11 Correct 17 ms 1920 KB Output is correct
12 Correct 20 ms 1920 KB Output is correct
13 Correct 23 ms 2040 KB Output is correct
14 Correct 20 ms 2048 KB Output is correct
15 Correct 20 ms 2048 KB Output is correct
16 Correct 17 ms 2032 KB Output is correct
17 Correct 17 ms 2048 KB Output is correct
18 Correct 943 ms 9928 KB Output is correct
19 Correct 1024 ms 10036 KB Output is correct
20 Correct 980 ms 9984 KB Output is correct
21 Correct 910 ms 10000 KB Output is correct
22 Correct 950 ms 9876 KB Output is correct
23 Correct 1536 ms 9628 KB Output is correct
24 Correct 1409 ms 9748 KB Output is correct
25 Correct 1351 ms 9720 KB Output is correct
26 Correct 94 ms 3820 KB Output is correct
27 Correct 1162 ms 9896 KB Output is correct
28 Correct 1036 ms 10028 KB Output is correct
29 Correct 632 ms 8540 KB Output is correct
30 Correct 757 ms 10452 KB Output is correct
31 Correct 726 ms 7852 KB Output is correct
32 Correct 571 ms 5032 KB Output is correct
33 Correct 803 ms 7808 KB Output is correct
34 Correct 803 ms 7808 KB Output is correct
35 Correct 91 ms 3816 KB Output is correct
36 Correct 754 ms 7828 KB Output is correct
37 Correct 605 ms 7700 KB Output is correct
38 Correct 512 ms 7736 KB Output is correct
39 Correct 342 ms 7156 KB Output is correct
40 Correct 311 ms 6932 KB Output is correct
41 Correct 487 ms 8136 KB Output is correct
42 Correct 450 ms 8048 KB Output is correct
43 Correct 1198 ms 11848 KB Output is correct
44 Correct 90 ms 3816 KB Output is correct
45 Correct 96 ms 9504 KB Output is correct
46 Correct 87 ms 9524 KB Output is correct
47 Correct 1157 ms 12000 KB Output is correct
48 Correct 1210 ms 11996 KB Output is correct
49 Correct 1218 ms 12020 KB Output is correct
50 Correct 479 ms 7964 KB Output is correct
51 Correct 463 ms 7976 KB Output is correct
52 Correct 450 ms 8028 KB Output is correct
53 Correct 869 ms 10472 KB Output is correct
54 Correct 792 ms 10812 KB Output is correct
55 Correct 814 ms 10756 KB Output is correct
56 Correct 1257 ms 11912 KB Output is correct
57 Correct 1100 ms 11956 KB Output is correct
58 Correct 1161 ms 11888 KB Output is correct
59 Correct 1163 ms 12056 KB Output is correct
60 Correct 1158 ms 11924 KB Output is correct
61 Correct 1164 ms 11816 KB Output is correct
62 Correct 984 ms 11172 KB Output is correct
63 Correct 912 ms 11176 KB Output is correct
64 Correct 1181 ms 11676 KB Output is correct
65 Correct 940 ms 10824 KB Output is correct
66 Correct 987 ms 9876 KB Output is correct
67 Correct 1476 ms 13032 KB Output is correct
68 Correct 1448 ms 18608 KB Output is correct
69 Correct 976 ms 12952 KB Output is correct
70 Correct 1543 ms 9928 KB Output is correct
71 Correct 1541 ms 10156 KB Output is correct
72 Correct 1481 ms 9904 KB Output is correct
73 Correct 1202 ms 10112 KB Output is correct
74 Correct 1284 ms 9968 KB Output is correct
75 Correct 1323 ms 10012 KB Output is correct
76 Correct 930 ms 10072 KB Output is correct
77 Correct 913 ms 9956 KB Output is correct
78 Correct 894 ms 10008 KB Output is correct
79 Correct 617 ms 9016 KB Output is correct
80 Correct 655 ms 9040 KB Output is correct
81 Correct 649 ms 9068 KB Output is correct
82 Correct 616 ms 10548 KB Output is correct
83 Correct 638 ms 10600 KB Output is correct
84 Correct 626 ms 10564 KB Output is correct
85 Correct 1566 ms 31304 KB Output is correct
86 Correct 111 ms 10920 KB Output is correct
87 Correct 120 ms 11088 KB Output is correct
88 Correct 1531 ms 14492 KB Output is correct
89 Correct 1551 ms 31868 KB Output is correct
90 Correct 1504 ms 14176 KB Output is correct
91 Correct 1257 ms 11024 KB Output is correct
92 Correct 1235 ms 10924 KB Output is correct
93 Correct 1605 ms 10288 KB Output is correct
94 Correct 1441 ms 14036 KB Output is correct
95 Correct 1457 ms 14488 KB Output is correct
96 Correct 1346 ms 12860 KB Output is correct
97 Correct 1226 ms 13336 KB Output is correct
98 Correct 1405 ms 14536 KB Output is correct
99 Correct 1600 ms 30488 KB Output is correct
100 Correct 1556 ms 30212 KB Output is correct
101 Correct 1613 ms 25608 KB Output is correct
102 Correct 1614 ms 25948 KB Output is correct
103 Correct 1369 ms 12700 KB Output is correct
104 Correct 1605 ms 12680 KB Output is correct
105 Correct 1203 ms 13300 KB Output is correct
106 Correct 1088 ms 13332 KB Output is correct
107 Correct 1109 ms 12056 KB Output is correct
108 Correct 1749 ms 24428 KB Output is correct
109 Correct 1382 ms 12308 KB Output is correct