Submission #249020

#	Time	Username	Problem	Language	Result	Execution time	Memory
249020		SamAnd	Bridges (APIO19_bridges)	C++17	43 / 100	744 ms	10488 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 100005;

struct ban
{
    int x, y, z;
};
int n_, m_, q_;
ban a_[N];
ban b_[N];

void ka()
{
    cin >> n_ >> m_;
    for (int i = 0; i < m_; ++i)
    {
        cin >> a_[i].x >> a_[i].y >> a_[i].z;
    }
    cin >> q_;
    for (int i = 0; i < q_; ++i)
    {
        cin >> b_[i].x >> b_[i].y >> b_[i].z;
    }
}

namespace solv1
{
    const int N = 1003;
    struct ban
    {
        int x, d;
        ban(){}
        ban(int x, int d)
        {
            this->x = x;
            this->d = d;
        }
    };

    int n, m, q;
    vector<ban> a[N];
    pair<int, int> b[N];
    pair<int, int> bb[N];

    bool c[N];
    void dfs(int x, int d)
    {
        c[x] = true;
        for (int i = 0; i < a[x].size(); ++i)
        {
            int h = a[x][i].x;
            if (!c[h] && d <= a[x][i].d)
                dfs(h, d);
        }
    }

    void solv()
    {
        n = n_;
        m = m_;
        for (int i = 1; i <= m; ++i)
        {
            int x, y, d;
            x = a_[i - 1].x;
            y = a_[i - 1].y;
            d = a_[i - 1].z;
            b[i] = m_p(x, y);
            bb[i].first = a[x].size();
            bb[i].second = a[y].size();
            a[x].push_back(ban(y, d));
            a[y].push_back(ban(x, d));
        }
        q = q_;
        for (int ii = 0; ii < q; ++ii)
        {
            int ty;
            ty = b_[ii].x;
            if (ty == 1)
            {
                int i, d;
                i = b_[ii].y;
                d = b_[ii].z;
                a[b[i].first][bb[i].first].d = d;
                a[b[i].second][bb[i].second].d = d;
            }
            else
            {
                int x, d;
                x = b_[ii].y;
                d = b_[ii].z;
                memset(c, false, sizeof c);
                dfs(x, d);
                int ans = 0;
                for (int i = 1; i <= n; ++i)
                {
                    if (c[i])
                        ++ans;
                }
                cout << ans << endl;
            }
        }
    }
};

namespace solv2
{
    const int N = 50004;

    int n, m, q;

    int t[N * 4];
    void ubd(int tl, int tr, int x, int y, int pos)
    {
        if (tl == tr)
        {
            t[pos] = y;
            return;
        }
        int m = (tl + tr) / 2;
        if (x <= m)
            ubd(tl, m, x, y, pos * 2);
        else
            ubd(m + 1, tr, x, y, pos * 2 + 1);
        t[pos] = min(t[pos * 2], t[pos * 2 + 1]);
    }
    int qry(int tl, int tr, int l, int r, int pos)
    {
        if (r < l)
            return 1000000009;
        if (tl == l && tr == r)
            return t[pos];
        int m = (tl + tr) / 2;
        if (r <= m)
            return qry(tl, m, l, r, pos * 2);
        if (l > m)
            return qry(m + 1, tr, l, r, pos * 2 + 1);
        return min(qry(tl, m, l, m, pos * 2), qry(m + 1, tr, m + 1, r, pos * 2 + 1));
    }

    void solv()
    {
        n = n_;
        m = m_;
        for (int i = 1; i <= m; ++i)
        {
            int x, y, d;
            x = a_[i - 1].x;
            y = a_[i - 1].y;
            d = a_[i - 1].z;
            ubd(1, n, i, d, 1);
        }
        q = q_;
        for (int ii = 0; ii < q; ++ii)
        {
            int ty;
            ty = b_[ii].x;
            if (ty == 1)
            {
                int i, d;
                i = b_[ii].y;
                d = b_[ii].z;
                ubd(1, n, i, d, 1);
            }
            else
            {
                int x, d;
                x = b_[ii].y;
                d = b_[ii].z;
                int l = x, r = n;
                while ((r - l) > 4)
                {
                    int m = (l + r) / 2;
                    if (qry(1, n, x, m - 1, 1) >= d)
                        l = m;
                    else
                        r = m;
                }
                int ans = 0;
                for (int m = r; m >= l; --m)
                {
                    if (qry(1, n, x, m - 1, 1) >= d)
                    {
                        ans += (m - x + 1);
                        break;
                    }
                }
                l = 1, r = x - 1;
                while ((r - l) > 4)
                {
                    int m = (l + r) / 2;
                    if (qry(1, n, m, x - 1, 1) >= d)
                        r = m;
                    else
                        l = m;
                }
                for (int m = l; m <= r; ++m)
                {
                    if (qry(1, n, m, x - 1, 1) >= d)
                    {
                        ans += (x - m);
                        break;
                    }
                }
                cout << ans << endl;
            }
        }
    }
};

namespace solv4
{
    const int N = 100005;
    struct ban
    {
        int x, y, d;
        ban(){}
        ban(int x, int y, int d)
        {
            this->x = x;
            this->y = y;
            this->d = d;
        }
    };
    bool operator<(const ban& a, const ban& b)
    {
        return a.d < b.d;
    }
    struct banq
    {
        int i;
        int x, d;
        banq(){}
        banq(int i, int x, int d)
        {
            this->i = i;
            this->x = x;
            this->d = d;
        }
    };
    bool operator<(const banq& a, const banq& b)
    {
        return a.d < b.d;
    }

    int n, m, q;
    ban a[N * 2];
    banq b[N * 2];

    int p[N], s[N];
    int fi(int x)
    {
        if (p[x] == x)
            return x;
        return p[x] = fi(p[x]);
    }
    void kpc(int x, int y)
    {
        x = fi(x);
        y = fi(y);
        if (s[x] < s[y])
        {
            p[x] = y;
            s[y] += s[x];
        }
        else
        {
            p[y] = x;
            s[x] += s[y];
        }
    }

    int ans[N * 2];

    void solv()
    {
        n = n_;
        m = m_;
        for (int i = 1; i <= m; ++i)
        {
            a[i].x = a_[i - 1].x;
            a[i].y = a_[i - 1].y;
            a[i].d = a_[i - 1].z;
        }
        q = q_;
        for (int i = 1; i <= q; ++i)
        {
            int ty;
            ty = b_[i - 1].x;
            b[i].x = b_[i - 1].y;
            b[i].d = b_[i - 1].z;
            b[i].i = i;
        }
        sort(a + 1, a + m + 1);
        reverse(a + 1, a + m + 1);
        sort(b + 1, b + q + 1);
        reverse(b + 1, b + q + 1);
        for (int i = 1; i <= n; ++i)
        {
            p[i] = i;
            s[i] = 1;
        }
        int j = 0;
        for (int i = 1; i <= q; ++i)
        {
            while (j != m && a[j + 1].d >= b[i].d)
            {
                ++j;
                if (fi(a[j].x) != fi(a[j].y))
                    kpc(a[j].x, a[j].y);
            }
            ans[b[i].i] = s[fi(b[i].x)];
        }
        for (int i = 1; i <= q; ++i)
            cout << ans[i] << endl;
    }
};

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);
    ka();
    if (n_ <= 1000 && m_ <= 1000 && q_ <= 10000)
    {
        solv1::solv();
        return 0;
    }
    bool z4 = true;
    for (int i = 0; i < q_; ++i)
    {
        if (b_[i].x == 1)
        {
            z4 = false;
            break;
        }
    }
    if (z4)
    {
        solv4::solv();
        return 0;
    }
    solv2::solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

bridges.cpp: In function 'void solv1::dfs(int, int)':
bridges.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
bridges.cpp: In function 'void solv2::solv()':
bridges.cpp:155:17: warning: variable 'x' set but not used [-Wunused-but-set-variable]
             int x, y, d;
                 ^
bridges.cpp:155:20: warning: variable 'y' set but not used [-Wunused-but-set-variable]
             int x, y, d;
                    ^
bridges.cpp: In function 'void solv4::solv()':
bridges.cpp:296:17: warning: variable 'ty' set but not used [-Wunused-but-set-variable]
             int ty;
                 ^~

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