oj.uz

Submission #249019

# Submission time Handle Problem Language Result Execution time Memory
249019 2020-07-14T06:14:59 Z SamAnd Bridges (APIO19_bridges) C++17
13 / 100
 79 ms 6520 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()
{
    scanf("%d%d", &n_, &m_);
    for (int i = 0; i < m_; ++i)
    {
        scanf("%d%d%d", &a_[i].x, &a_[i].y, &a_[i].z);
    }
    scanf("%d", &q_);
    for (int i = 0; i < q_; ++i)
    {
        scanf("%d%d%d", &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()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; ++i)
        {
            int x, y, d;
            cin >> x >> y >> d;
            ubd(1, n, i, d, 1);
        }
        cin >> q;
        while (q--)
        {
            int ty;
            cin >> ty;
            if (ty == 1)
            {
                int i, d;
                cin >> i >> d;
                ubd(1, n, i, d, 1);
            }
            else
            {
                int x, d;
                cin >> x >> d;
                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()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; ++i)
        {
            cin >> a[i].x >> a[i].y >> a[i].d;
        }
        cin >> q;
        for (int i = 1; i <= q; ++i)
        {
            int ty;
            cin >> ty;
            cin >> b[i].x >> b[i].d;
            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;
}

//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 ka()':
bridges.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n_, &m_);
     ~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a_[i].x, &a_[i].y, &a_[i].z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q_);
     ~~~~~^~~~~~~~~~~
bridges.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &b_[i].x, &b_[i].y, &b_[i].z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 51 ms 760 KB Output is correct
4 Correct 23 ms 668 KB Output is correct
5 Correct 18 ms 640 KB Output is correct
6 Correct 16 ms 640 KB Output is correct
7 Correct 17 ms 640 KB Output is correct
8 Correct 26 ms 640 KB Output is correct
9 Correct 28 ms 640 KB Output is correct
10 Correct 24 ms 640 KB Output is correct
11 Correct 24 ms 640 KB Output is correct
12 Correct 15 ms 640 KB Output is correct
13 Correct 18 ms 640 KB Output is correct
14 Correct 18 ms 640 KB Output is correct
15 Correct 21 ms 640 KB Output is correct
16 Correct 17 ms 640 KB Output is correct
17 Correct 16 ms 640 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 51 ms 760 KB Output is correct
4 Correct 23 ms 668 KB Output is correct
5 Correct 18 ms 640 KB Output is correct
6 Correct 16 ms 640 KB Output is correct
7 Correct 17 ms 640 KB Output is correct
8 Correct 26 ms 640 KB Output is correct
9 Correct 28 ms 640 KB Output is correct
10 Correct 24 ms 640 KB Output is correct
11 Correct 24 ms 640 KB Output is correct
12 Correct 15 ms 640 KB Output is correct
13 Correct 18 ms 640 KB Output is correct
14 Correct 18 ms 640 KB Output is correct
15 Correct 21 ms 640 KB Output is correct
16 Correct 17 ms 640 KB Output is correct
17 Correct 16 ms 640 KB Output is correct
18 Incorrect 58 ms 4600 KB Output isn't correct
19 Halted 0 ms 0 KB -