Submission #413461

#	Time	Username	Problem	Language	Result	Execution time	Memory
413461		arayi	Bridges (APIO19_bridges)	C++17	27 / 100	3113 ms	403400 KiB

bridges

//Arayi
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>   
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cassert>
#include <chrono>
#include <random>
#include <complex>

#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;

lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
    return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
    return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = { 'a', 'e', 'i', 'o', 'u' };
int dx[] = { 0, -1, 0, 1, -1, -1, 1, 1, 0 };
int dy[] = { -1, 0, 1, 0, -1, 1, -1, 1, 0 };


const int N = 1e5 + 30;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const int T = 200;

lli bp(lli a, lli b = mod - 2LL)
{
    lli ret = 1;
    while (b)
    {
        if (b & 1) ret *= a, ret %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ret;
}
ostream& operator<<(ostream& c, pir a)
{
    c << a.fr << " " << a.sc;
    return c;
}
template<class T>
void maxi(T& a, T b)
{
    a = max(a, b);
}
template <class T>
void mini(T& a, T b)
{
    a = min(a, b);
}



int n, m, q, cl;
int a[N], b[N], c[N], pat[N], col[N];
int p[N / T + 3][N], sz[N / T + 3][N];
vector<pir> l[N / T + 3];
vector<pir> g[N];
int gp(int i1, int x)
{
    if (p[i1][x] == x) return x;
    return p[i1][x] = gp(i1, p[i1][x]);
}
void lil(int i1, int a, int b)
{
    //cout << a << " " << b << endl;
    a = gp(i1, a), b = gp(i1, b);
    if (a == b) return;
    if (sz[i1][a] > sz[i1][b]) p[i1][b] = a, sz[i1][a] += sz[i1][b];
    else p[i1][a] = b, sz[i1][b] += sz[i1][a];
}
int dfs(int i1, int v, int w)
{
    //cout << v << endl;
    col[v] = cl;
    int ret = sz[i1][v];
    for (auto p : g[v])
    {
        if (col[p.fr] == cl || c[p.sc] < w) continue;
        ret += dfs(i1, p.fr, w);
    }
    return ret;
}
int main()
{
    fastio;
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i];
    for (int i = 0; i < N / T + 3; i++)
        for (int j = 0; j <= n; j++) p[i][j] = j, sz[i][j] = 1;
    cin >> q;
    vector<pir> t;
    vector<pair<pir, pir> > fp;
    for (int i = 0; i < q; i++)
    {
        int A;
        cin >> A;
        if (A == 1)
        {
            int b, c;
            cin >> b >> c;
            t.ad(MP(c, b - 1));
        }
        else
        {
            int s, c;
            cin >> s >> c;
            fp.ad(MP(MP(c, s), MP(t.size(), i)));
        }
    }
    vector<pair<int, pir> > f;
    for (int i = 0; i < t.size(); i++)
    {
        if (i % T == 0)
        {
            unordered_set<int> s;
            for (int j = i; j < min(i + T, (int)t.size()); j++)
                s.insert(t[j].sc);
            for (int j = 0; j < m; j++)
            {
                if (s.find(j) != s.end()) l[i / T].ad(MP(j, c[j]));
                else f.ad(MP(c[j], MP(j, i / T)));
            }
        }
        c[t[i].sc] = t[i].fr;
    }
    if ((int)t.size() % T == 0)
        for (int j = 0; j < m; j++) f.ad(MP(c[j], MP(j, (int)t.size() / T)));
    int i1 = 0;
    sort(all(fp)), sort(all(f));
    reverse(all(fp)), reverse(all(f));
    //for (auto p : f) cout << p.fr << " " << p.sc << endl;
    //for (auto p : fp) cout << p.fr << " " << p.sc << endl;
    for (int i = 0; i < fp.size(); i++)
    {
        while (i1 < f.size() && f[i1].fr >= fp[i].fr.fr)
        {
            lil(f[i1].sc.sc, a[f[i1].sc.fr], b[f[i1].sc.fr]);
            i1++;
        }
        int s = fp[i].fr.sc;
        int j = fp[i].sc.fr;
        int ii = j / T;
        for (auto p : l[ii]) c[p.fr] = p.sc, g[gp(ii, a[p.fr])].ad(MP(gp(ii, b[p.fr]), p.fr)), g[gp(ii, b[p.fr])].ad(MP(gp(ii, a[p.fr]), p.fr));
        for (int k = ii * T; k < j; k++) c[t[k].sc] = t[k].fr;
        cl++;
        pat[fp[i].sc.sc] = dfs(ii, gp(ii, s), fp[i].fr.fr);
        for (auto p : l[ii]) g[gp(ii, a[p.fr])].clear(), g[gp(ii, b[p.fr])].clear();
    }
    for (int i = 0; i < q; i++)
        if (pat[i]) cout << pat[i] << "\n";
    return 0;
}

/*
    __
  *(><)*
    \/ /
    ||/
  --||
    ||
    /\
   /  \
  /    \

*/

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 0; i < t.size(); i++)
      |                     ~~^~~~~~~~~~
bridges.cpp:177:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (int i = 0; i < fp.size(); i++)
      |                     ~~^~~~~~~~~~~
bridges.cpp:179:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |         while (i1 < f.size() && f[i1].fr >= fp[i].fr.fr)
      |                ~~~^~~~~~~~~~

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