Submission #911123

#	Time	Username	Problem	Language	Result	Execution time	Memory
911123		duckindog	Bridges (APIO19_bridges)	C++14	14 / 100	87 ms	17584 KiB

bridges

// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10;
struct edge {
  int u, v, w;
  edge() : u(0), v(0), w(0) {}
  edge(int u, int v, int w) : u(u), v(v), w(w) {}
} ed[N];
int n, m;
vector<int> ad[N];

bool dd[N];
int bfs(int x, int mw) {
  memset(dd, 0, sizeof dd);
  queue<int> q;
  q.push(x); dd[x] = 1;
  while (q.size()) {
    int pre = q.front(); q.pop();
    for (auto i : ad[pre]) {
      int u = ed[i].u, v = ed[i].v, w = ed[i].w;
      if (v == pre) swap(u, v);
      if (dd[v] || w < mw) continue;
      dd[v] = 1;
      q.push(v);
    }

  }


  int cnt = 0;
  for (int i = 1; i <= n; ++i) cnt += dd[i];
  return cnt;
}

void sub1() {

  int q; cin >> q;
  while (q--) {
    int ty; cin >> ty;
    if (ty == 1) {
      int i, nw; cin >> i >> nw;
      ed[i].w = nw;

    } else {
      int s, w; cin >> s >> w;

      cout << bfs(s, w) << '\n';

    }

  }

}

int T[4 * N];
void build(int s, int l, int r) {
  if (l == r) {
    T[s] = ed[l].w;
    return;
  }
  int mid = l + r >> 1;
  build(s * 2, l, mid); build(s * 2 + 1, mid + 1, r);
  T[s] = min(T[s * 2], T[s * 2 + 1]);
}
void update(int s, int l, int r, int x, int y) {
  if (y < l || y > r) return;
  if (l == r) {
    T[s] = x;
    return;
  }
  int mid = l + r >> 1;
  update(s * 2, l, mid, x, y); update(s * 2 + 1, mid + 1, r, x, y);
  T[s] = min(T[s * 2], T[s * 2 + 1]);
}
int query(int s, int l, int r, int u, int v) {
  if (v < l || u > r) return 1e9;
  if (u <= l && r <= v) return T[s];
  int mid = l + r >> 1;
  return min(query(s * 2, l, mid, u, v), query(s * 2 + 1, mid + 1, r, u, v));
}
void sub2() {
  build(1, 1, m);

  int q; cin >> q;
  while (q--) {
    int ty; cin >> ty;
    if (ty == 1) {
      int i, w; cin >> i >> w;
      update(1, 1, m, w, i);
    } else {
      int i, w; cin >> i >> w;

      int answer = 0;
      int l = 1, r = i - 1, it = i;

      while (l <= r) {
        int mid = l + r >> 1;
        if (query(1, 1, m, mid, i - 1) >= w) r = (it = mid) - 1;
        else l = mid + 1;
      }
      answer += (i - it + 1);

      l = i, r = m, it = i - 1;
      while (l <= r) {
        int mid = l + r >> 1;
        if (query(1, 1, m, i, mid) >= w) l = (it = mid) + 1;
        else r = mid - 1;
      }
      answer += (it - i + 1);

      cout << answer << '\n';
    }

  }
}

tuple<int, int, int> Q[N];
int par[N];
int root(int u) {
  return (par[u] < 0 ? u : par[u] = root(par[u]));
}
void add(int u, int v) {
  u = root(u); v = root(v);
  if (u == v) return;
  if (par[u] > par[v]) swap(u, v);
  par[u] += par[v];
  par[v] = u;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }

  cin >> n >> m;
  bool chain = 1;

  for (int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    ed[i] = {u, v, w};
    ad[u].push_back(i);
    ad[v].push_back(i);
    if (ad[u].size() > 2 || ad[v].size() > 2) chain = 0;
  }

//  if (n <= 1e3 && m <= 1e3) {
//    sub1();
//    return 0;
//  }

//  if (chain) {
//    sub2();
//    return 0;
//  }


  int q; cin >> q;
  bool query_only = 1;
  for (int i = 1; i <= q; ++i) {
    int ty, s, w; cin >> ty >> s >> w;
    if (ty == 1) query_only = 0;
    Q[i] = make_tuple(w, s, i);
  }


  if (query_only) {
    memset(par, -1, sizeof par);
    sort(Q + 1, Q + q + 1, greater<>());
    sort(ed + 1, ed + m + 1, [&] (edge a, edge b) {
      return a.w < b.w;
    });

    int it = m;
    vector<int> answer(q + 1);
    for (int i = 1; i <= q; ++i) {
      int w, s, t; tie(w, s, t) = Q[i];

      while (ed[it].w >= w) {
        add(ed[it].u, ed[it].v);
        it -= 1;
      }

      answer[t] = -par[root(s)];
    }
    for (int i = 1; i <= q; ++i) cout << answer[i] << '\n';
    return 0;
  }


}

Compilation message (stderr)

bridges.cpp: In function 'void build(long long int, long long int, long long int)':
bridges.cpp:66:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   int mid = l + r >> 1;
      |             ~~^~~
bridges.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
bridges.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int mid = l + r >> 1;
      |             ~~^~~
bridges.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
bridges.cpp:83:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |   int mid = l + r >> 1;
      |             ~~^~~
bridges.cpp: In function 'void sub2()':
bridges.cpp:102:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         int mid = l + r >> 1;
      |                   ~~^~~
bridges.cpp:110:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid = l + r >> 1;
      |                   ~~^~~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:144:8: warning: variable 'chain' set but not used [-Wunused-but-set-variable]
  144 |   bool chain = 1;
      |        ^~~~~
bridges.cpp:139:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:140:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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