oj.uz

Submission #211529

# Submission time Handle Problem Language Result Execution time Memory
211529 2020-03-20T16:51:52 Z VEGAnn Bridges (APIO19_bridges) C++14
44 / 100
 3000 ms 178100 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 78 ms 13560 KB Output is correct
4 Correct 12 ms 5452 KB Output is correct
5 Correct 27 ms 7032 KB Output is correct
6 Correct 26 ms 7040 KB Output is correct
7 Correct 30 ms 6904 KB Output is correct
8 Correct 28 ms 6784 KB Output is correct
9 Correct 36 ms 7936 KB Output is correct
10 Correct 29 ms 7032 KB Output is correct
11 Correct 28 ms 6904 KB Output is correct
12 Correct 33 ms 7416 KB Output is correct
13 Correct 39 ms 7932 KB Output is correct
14 Correct 35 ms 7544 KB Output is correct
15 Correct 37 ms 7544 KB Output is correct
16 Correct 32 ms 7288 KB Output is correct
17 Correct 31 ms 7288 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2354 ms 90692 KB Output is correct
2 Correct 2301 ms 90660 KB Output is correct
3 Correct 2310 ms 90852 KB Output is correct
4 Correct 2357 ms 90268 KB Output is correct
5 Correct 2386 ms 91132 KB Output is correct
6 Execution timed out 3088 ms 178100 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2104 ms 88396 KB Output is correct
2 Correct 1652 ms 142840 KB Output is correct
3 Correct 2516 ms 150424 KB Output is correct
4 Correct 1991 ms 88160 KB Output is correct
5 Correct 54 ms 8184 KB Output is correct
6 Correct 2293 ms 110968 KB Output is correct
7 Correct 1767 ms 81040 KB Output is correct
8 Correct 1517 ms 61592 KB Output is correct
9 Correct 1183 ms 49400 KB Output is correct
10 Correct 1008 ms 37728 KB Output is correct
11 Correct 1412 ms 45768 KB Output is correct
12 Correct 1224 ms 35964 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2422 ms 18808 KB Output is correct
2 Correct 56 ms 8184 KB Output is correct
3 Correct 255 ms 13580 KB Output is correct
4 Correct 107 ms 13688 KB Output is correct
5 Correct 1561 ms 17156 KB Output is correct
6 Correct 2743 ms 18608 KB Output is correct
7 Correct 1459 ms 17200 KB Output is correct
8 Correct 1142 ms 14200 KB Output is correct
9 Correct 1124 ms 14244 KB Output is correct
10 Correct 1104 ms 14200 KB Output is correct
11 Correct 1664 ms 16168 KB Output is correct
12 Correct 1663 ms 16308 KB Output is correct
13 Correct 1664 ms 16628 KB Output is correct
14 Correct 1057 ms 17272 KB Output is correct
15 Correct 1168 ms 17412 KB Output is correct
16 Correct 2347 ms 18804 KB Output is correct
17 Correct 2364 ms 18696 KB Output is correct
18 Correct 2345 ms 18760 KB Output is correct
19 Correct 2281 ms 18684 KB Output is correct
20 Correct 2013 ms 17108 KB Output is correct
21 Correct 2028 ms 17036 KB Output is correct
22 Correct 2250 ms 18304 KB Output is correct
23 Correct 1859 ms 15540 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2354 ms 90692 KB Output is correct
2 Correct 2301 ms 90660 KB Output is correct
3 Correct 2310 ms 90852 KB Output is correct
4 Correct 2357 ms 90268 KB Output is correct
5 Correct 2386 ms 91132 KB Output is correct
6 Execution timed out 3088 ms 178100 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 78 ms 13560 KB Output is correct
4 Correct 12 ms 5452 KB Output is correct
5 Correct 27 ms 7032 KB Output is correct
6 Correct 26 ms 7040 KB Output is correct
7 Correct 30 ms 6904 KB Output is correct
8 Correct 28 ms 6784 KB Output is correct
9 Correct 36 ms 7936 KB Output is correct
10 Correct 29 ms 7032 KB Output is correct
11 Correct 28 ms 6904 KB Output is correct
12 Correct 33 ms 7416 KB Output is correct
13 Correct 39 ms 7932 KB Output is correct
14 Correct 35 ms 7544 KB Output is correct
15 Correct 37 ms 7544 KB Output is correct
16 Correct 32 ms 7288 KB Output is correct
17 Correct 31 ms 7288 KB Output is correct
18 Correct 2354 ms 90692 KB Output is correct
19 Correct 2301 ms 90660 KB Output is correct
20 Correct 2310 ms 90852 KB Output is correct
21 Correct 2357 ms 90268 KB Output is correct
22 Correct 2386 ms 91132 KB Output is correct
23 Execution timed out 3088 ms 178100 KB Time limit exceeded
24 Halted 0 ms 0 KB -