Submission #211529

#	Time	Username	Problem	Language	Result	Execution time	Memory
211529		VEGAnn	Bridges (APIO19_bridges)	C++14	44 / 100	3088 ms	178100 KiB

bridges

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
 
using namespace std;
 
typedef long long ll;
 
#ifdef ONPC
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
 
const int BLOCK = 1100;
 
const int N = 1e5 + 7;
 
int dsu[N];
int sz[N];
bool bad[N];
int ind[N];
int w[N];
int u[N], v[N];
 
inline int get(int v)
{
  if (v == dsu[v])
  {
    return v;
  }
  else
  {
    return dsu[v] = get(dsu[v]);
  }
}
 
inline void uni(int u, int v)
{
  u = get(u), v = get(v);
  if (u == v) return;
  if (sz[u] > sz[v]) swap(u, v);
  dsu[u] = v;
  sz[v] += sz[u];
}
 
int gays[N];
int spanning[N];
int was_id[N];
int par[N];
bool vis[N];
int ans[N];
vector <int> events[N];
vector <pair <int, int> > gr[N];
int predok[N];
bool flex[N];
 
int microdsu[N];
int microsz[N];
int micrornk[N];
 
inline int microget(int v)
{
  if (v == microdsu[v])
  {
    return v;
  }
  else
  {
    return microdsu[v] = microget(microdsu[v]);
  }
}
 
inline void microuni(int u, int v)
{
  u = microget(u);
  v = microget(v);
  if (u == v) return;
  if (micrornk[u] > micrornk[v]) swap(u, v);
  if (micrornk[u] ==micrornk[v]) micrornk[v]++;
  microsz[v] += microsz[u];
  microdsu[u] = v;
}
 
int main()
{
#ifdef ONPC
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n = 50000, m = 49999;
  int inf = 1e9;
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    microdsu[i] = i;
    microsz[i] = 1;
  }
  for (int i = 0; i < m; i++)
  {
    u[i] = rnd() % n, v[i] = rnd() % n;
    w[i] = rnd() % inf;
    cin >> u[i] >> v[i] >> w[i];
    u[i]--, v[i]--;
    ind[i] = i;
    w[i] *= -1;
  }
  int q = 100000;
  cin >> q;
  vector <int> t(q), a(q), b(q);
  for (int i = 0; i < q; i++)
  {
    cin >> t[i] >> a[i] >> b[i];
    a[i]--;
  //  t[i] = rnd() % 2 + 1;
    //t[i] = rnd() % 2 + 1;
    //a[i] = rnd() % n;
    //b[i] = rnd() % inf;
    //a[i]--;
    b[i] *= -1;
  }
  //for (int i = 0; i < q; i++) events[i].reserve(2 * BLOCK);
  for (int i = 0; i < n; i++)
  {
    dsu[i] = i;
    sz[i] = 1;
  }
  set <pair <int, int> > glob;
  for (int i = 0; i < m; i++)
  {
    glob.insert({w[i], i});
  }
  vector <pair <int, int> > e;
  int sum = 0;
  for (int i = 0; i < q; i += BLOCK)
  {
    for (int i = 0; i < m; i++) bad[i] = 0, flex[i] = 0;
    int l = i, r = min(q, i + BLOCK);
    for (int ptr = l; ptr < r; ptr++)
    {
      if (t[ptr] == 1)
      {
        glob.erase({w[a[ptr]], a[ptr]});
        bad[a[ptr]] = 1;
      }
    }
    for (int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
    double was = clock();
    auto it = glob.begin();
    for (auto &c : glob)
    {
      int id = c.second;
      if (get(u[id]) != get(v[id]))
      {
        uni(u[id], v[id]);
        flex[id] = true;
      }
    }
    double now = clock();
    for (int i = 0; i < n; i++) dsu[i] = i,sz[i] = 1;
    set <pair <int, int> > q;
    for (int ptr = l; ptr < r; ptr++)
    {
      if (t[ptr] == 1)
      {
        glob.insert({-inf, a[ptr]});
      }
    }
    int span_len = 0;
    for (auto &c : glob)
    {
      int id = c.second;
      if (get(u[id]) != get(v[id]))
      {
        uni(u[id], v[id]);
        flex[id] = false;
        if (!bad[id])
        {
          spanning[span_len++] = id;
        }
      }
    }
    for (int ptr = l; ptr < r; ptr++)
    {
      if (t[ptr] == 1)
      {
        glob.erase({-inf, a[ptr]});
      }
    }
    for (int ptr = l; ptr < r; ptr++)
    {
      if (t[ptr] == 1)
      {
        glob.insert({w[a[ptr]], a[ptr]});
      }
    }
    for (int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
    for (int i = 0; i < m; i++)
    {
      if (bad[i] || flex[i])
      {
        q.insert({w[i], i});
        sum++;
      }
    }
    e.clear();
    for (int ptr = l; ptr < r; ptr++)
    {
      if (t[ptr] == 1)
      {
        glob.erase({w[a[ptr]], a[ptr]});
        q.erase({w[a[ptr]], a[ptr]});
        w[a[ptr]] = b[ptr];
        q.insert({w[a[ptr]], a[ptr]});
        glob.insert({w[a[ptr]], a[ptr]});
      }
      else
      {
        for (auto &c : q)
        {
          if (c.first > b[ptr]) break;
          events[ptr].push_back(c.second);
        }
        e.push_back({b[ptr], ptr});
      }
    }
    sort(e.begin(), e.end());
    for (int i = 0; i < n; i++)
    {
      dsu[i] = i;
      sz[i] = 1;
    }
    int _st = -1;
    for (int i = 0; i <= span_len; i++)
    {
      while (_st + 1 < (int) e.size() && (i == span_len || e[_st + 1].first < w[spanning[i]]))
      {
        _st++;
        int id = e[_st].second;
        micrornk[get(a[id])] = 1;
        microsz[get(a[id])] = sz[get(a[id])];
        microdsu[get(a[id])] = get(a[id]);
        for (int x : events[id])
        {
          int l = get(u[x]);
          micrornk[l] = 1;
          microdsu[l] = l;
          microsz[l] = sz[l];
          l = get(v[x]);
          micrornk[l] = 1;
          microdsu[l] = l;
          microsz[l] = sz[l];
        }
        for (int x : events[id])
        {
          sum++;
          microuni(get(u[x]), get(v[x]));
        }
        ans[id] = microsz[microget(get(a[id]))];
      }
      if (i == span_len) break;
      uni(u[spanning[i]], v[spanning[i]]);
    }
  }
  for (int i = 0; i < q; i++)
  {
    if (t[i] == 2)
    {
      cout << ans[i] << '\n';
    }
  }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:148:12: warning: unused variable 'was' [-Wunused-variable]
     double was = clock();
            ^~~
bridges.cpp:149:10: warning: variable 'it' set but not used [-Wunused-but-set-variable]
     auto it = glob.begin();
          ^~
bridges.cpp:159:12: warning: unused variable 'now' [-Wunused-variable]
     double now = clock();
            ^~~

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