oj.uz

Submission #249020

# Submission time Handle Problem Language Result Execution time Memory
249020 2020-07-14T06:20:18 Z SamAnd Bridges (APIO19_bridges) C++17
43 / 100
 744 ms 10488 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 50 ms 632 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 16 ms 512 KB Output is correct
7 Correct 16 ms 512 KB Output is correct
8 Correct 16 ms 512 KB Output is correct
9 Correct 18 ms 512 KB Output is correct
10 Correct 14 ms 512 KB Output is correct
11 Correct 14 ms 512 KB Output is correct
12 Correct 16 ms 512 KB Output is correct
13 Correct 17 ms 512 KB Output is correct
14 Correct 16 ms 512 KB Output is correct
15 Correct 19 ms 512 KB Output is correct
16 Correct 16 ms 512 KB Output is correct
17 Correct 16 ms 512 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 2776 KB Output is correct
2 Correct 430 ms 5368 KB Output is correct
3 Correct 429 ms 5664 KB Output is correct
4 Correct 421 ms 5240 KB Output is correct
5 Correct 426 ms 5624 KB Output is correct
6 Correct 462 ms 5368 KB Output is correct
7 Correct 460 ms 5368 KB Output is correct
8 Correct 457 ms 5368 KB Output is correct
9 Correct 218 ms 4728 KB Output is correct
10 Correct 413 ms 4472 KB Output is correct
11 Correct 410 ms 4476 KB Output is correct
12 Correct 744 ms 5624 KB Output is correct
13 Correct 148 ms 5368 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 400 ms 2576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 6284 KB Output is correct
2 Correct 260 ms 4728 KB Output is correct
3 Correct 66 ms 4984 KB Output is correct
4 Correct 55 ms 4992 KB Output is correct
5 Correct 247 ms 8696 KB Output is correct
6 Correct 275 ms 10488 KB Output is correct
7 Correct 239 ms 8696 KB Output is correct
8 Correct 252 ms 7800 KB Output is correct
9 Correct 247 ms 7672 KB Output is correct
10 Correct 244 ms 7544 KB Output is correct
11 Correct 265 ms 8824 KB Output is correct
12 Correct 257 ms 8824 KB Output is correct
13 Correct 257 ms 8824 KB Output is correct
14 Correct 243 ms 8824 KB Output is correct
15 Correct 248 ms 8696 KB Output is correct
16 Correct 276 ms 9976 KB Output is correct
17 Correct 272 ms 9976 KB Output is correct
18 Correct 277 ms 10104 KB Output is correct
19 Correct 286 ms 10232 KB Output is correct
20 Correct 273 ms 9208 KB Output is correct
21 Correct 270 ms 9208 KB Output is correct
22 Correct 282 ms 9976 KB Output is correct
23 Correct 256 ms 8056 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 2776 KB Output is correct
2 Correct 430 ms 5368 KB Output is correct
3 Correct 429 ms 5664 KB Output is correct
4 Correct 421 ms 5240 KB Output is correct
5 Correct 426 ms 5624 KB Output is correct
6 Correct 462 ms 5368 KB Output is correct
7 Correct 460 ms 5368 KB Output is correct
8 Correct 457 ms 5368 KB Output is correct
9 Correct 218 ms 4728 KB Output is correct
10 Correct 413 ms 4472 KB Output is correct
11 Correct 410 ms 4476 KB Output is correct
12 Correct 744 ms 5624 KB Output is correct
13 Correct 148 ms 5368 KB Output is correct
14 Incorrect 400 ms 2576 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 50 ms 632 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 16 ms 512 KB Output is correct
6 Correct 16 ms 512 KB Output is correct
7 Correct 16 ms 512 KB Output is correct
8 Correct 16 ms 512 KB Output is correct
9 Correct 18 ms 512 KB Output is correct
10 Correct 14 ms 512 KB Output is correct
11 Correct 14 ms 512 KB Output is correct
12 Correct 16 ms 512 KB Output is correct
13 Correct 17 ms 512 KB Output is correct
14 Correct 16 ms 512 KB Output is correct
15 Correct 19 ms 512 KB Output is correct
16 Correct 16 ms 512 KB Output is correct
17 Correct 16 ms 512 KB Output is correct
18 Correct 434 ms 2776 KB Output is correct
19 Correct 430 ms 5368 KB Output is correct
20 Correct 429 ms 5664 KB Output is correct
21 Correct 421 ms 5240 KB Output is correct
22 Correct 426 ms 5624 KB Output is correct
23 Correct 462 ms 5368 KB Output is correct
24 Correct 460 ms 5368 KB Output is correct
25 Correct 457 ms 5368 KB Output is correct
26 Correct 218 ms 4728 KB Output is correct
27 Correct 413 ms 4472 KB Output is correct
28 Correct 410 ms 4476 KB Output is correct
29 Correct 744 ms 5624 KB Output is correct
30 Correct 148 ms 5368 KB Output is correct
31 Incorrect 400 ms 2576 KB Output isn't correct
32 Halted 0 ms 0 KB -