Submission #888502

#	Time	Username	Problem	Language	Result	Execution time	Memory
888502		rukashii	Bridges (APIO19_bridges)	C++17	0 / 100	74 ms	17468 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
 
#define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
#define int long long
#define f first
#define s second
 
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
    if (s.size()) setIn(s+".inp"), setOut(s+".out");
}
 
const int allmaxn = 5e4 + 2, allmaxm = 1e5 + 2;
 
int n, m, q;
vector <pair <int, int>> adj[allmaxn];
tuple <int, int, int> edges[allmaxm], Q[allmaxm];
 
namespace Sub1
{
    const int s1maxn = 1002;
 
    multiset <pair <int, int>> msadj[s1maxn];
    bool vis[s1maxn];
 
    bool Check()
    {
        return (n <= 1000 && m <= 1000 && q <= 10000);
    }
 
    void solve()
    {
        for (int i = 1; i <= n; i++)
        {
            for (auto [v, w] : adj[i])
            {
                msadj[i].insert({v, w});
            }
        }
 
        for (int i = 1; i <= q; i++)
        {
            auto [type, fi, se] = Q[i];
            if (type == 1)
            {
                int b = fi, r = se;
                auto [u, v, w] = edges[fi];
 
                msadj[u].erase(msadj[u].find({v, w}));
                msadj[v].erase(msadj[v].find({u, w}));
 
                msadj[u].insert({v, r});
                msadj[v].insert({u, r});
 
                edges[fi] = {u, v, r};
            }
            else
            {
                int st = fi, mxw = se;
 
                memset(vis, 0, sizeof(vis));
                queue <int> q;
                q.push(st);
                vis[st] = 1;
                int ans = 1;
 
                while (q.size())
                {
                    int u = q.front();
                    q.pop();
 
                    for (auto [v, w] : msadj[u])
                    {
                        if (w >= mxw && !vis[v])
                        {
                            vis[v] = 1;
                            q.push(v);
                            ans++;
                        }
                    }
                }
 
                cout << ans << '\n';
            }
        }
    }
} // namespace Sub1
 
namespace Sub2
{
    bool Check()
    {
        if (m != n - 1)
            return 0;
        for (int i = 1; i <= m; i++)
        {
            auto [u, v, w] = edges[i];
            if (u != v - 1)
                return 0;
        }
 
        return 1;
    }
 
    const int s2maxn = allmaxn;
 
    int tree[s2maxn * 4 + 10];
    int a[s2maxn + 10];
 
    void update(int id, int l, int r, int pl, int val)
    {
        if (pl > r || pl < l)
            return;
        if (l == r)
        {
            tree[id] = val;
            return;
        }
 
        int mid = (l + r) / 2;
 
        update(id * 2, l, mid, pl, val);
        update(id * 2 + 1, mid + 1, r, pl, val);
 
        tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
    }
 
    int getL(int id, int l, int r, int v, int val)
    {
        if (l > v)
            assert(0);
        
        if (r <= v)
        {
            int best = n + 1;
            while (1)
            {
                int L = id * 2, R = id * 2 + 1;
                int mid = (l + r) / 2;
                if (l == r)
                    return (a[l] >= val ? l : best);

                if (tree[R] >= val)
                {
                    best = mid + 1;
                    r = mid;
                    id = L;
                }
                else
                {
                    l = mid + 1;
                    id = R;
                }
            }
        }

        int mid = (l + r) / 2;
        int L = id * 2, R = id * 2 + 1;
        if (v <= mid)
            return getL(L, l, mid, v, val); // ans must be in the left
        
        if (getL(R, mid + 1, r, v, val) > mid + 1) // if there's an answer int the right
            return getL(R, mid + 1, r, v, val);
        return min(mid + 1, getL(L, l, mid, v, val));
    }
 
    int getR(int id, int l, int r, int u, int val)
    {
        if (r < u)
            return -1;
        
        if (l >= u)
        {
            int best = -1;
            while (1)
            {
                int L = id * 2, R = id * 2 + 1, mid = (l + r) / 2;
                if (l == r)
                    return (tree[id] >= val ? l : best);
                
                if (tree[L] >= val)
                {
                    best = mid;
                    l = mid + 1;
                    id = id * 2 + 1;
                }
                else
                {
                    r = mid;
                    id = id * 2;
                }
            }
        }

        int mid = (l + r) / 2;
        int L = id * 2, R = id * 2 + 1;
        if (mid + 1 <= u)
            return getR(R, mid + 1, r, u, val); 
        
        int tmp = getR(L, l, mid, u, val);
        if (tmp < mid)
            return tmp;
        return max(tmp, getR(R, mid + 1, r, u, val));
    }
 
    void solve()
    {
        // assert(0);
        for (int i = 1; i <= m; i++)
        {
            a[i] = get <2> (edges[i]);
            update(1, 1, n, i, a[i]);
        }
 
        for (int i = 1; i <= q; i++)
        {
            auto [type, fi, se] = Q[i];
            if (type == 1)
            {
                a[fi] = se;
                update(1, 1, n, fi, se);
            }
            else
            {
                int Lbor = fi, Rbor = fi;
                if (fi > 1)
                {
                    Lbor = min(getL(1, 1, n, fi - 1, se), Lbor);
                }
                if (fi < n)
                {
                    Rbor = max(getR(1, 1, n, fi, se) + 1, Rbor);
                }

                // cout << Lbor << ' ' << Rbor << '\n';
                cout << Rbor - Lbor + 1 << '\n';
            }
        }
    }
} // namespace Sub2
 
namespace Sub3
{
    bool Check()
    {
        for (int i = 1; i <= q; i++)
            if (get <0> (Q[i]) == 1)
                return 0;
        
        return 1;
    }

    const int s3maxn = allmaxn, s3maxq = allmaxm;

    int lab[s3maxn], sz[s3maxn], ans[s3maxq];
    tuple <int, int, int> queries[s3maxq];

    int get(int u)
    {
        return (lab[u] == -1) ? u : (lab[u] = get(lab[u]));
    }

    void merge(int u, int v)
    {
        int uu = get(u), vv = get(v);

        if (uu == vv)
            return;
        
        sz[uu] += sz[vv];
        sz[vv] = 0;
        lab[v] = u;
    }

    bool cmp(const tuple <int, int, int> &a, const tuple <int, int, int> &b)
    {
        auto [u1, v1, w1] = a;
        auto [u2, v2, w2] = b;
        return (w1 > w2);
    }

    void solve()
    {
        for (int i = 1; i <= q; i++)
        {
            auto [t, s, w] = Q[i];
            queries[i] = {w, s, i};
        }

        sort(queries + 1, queries + 1 + q);
        sort(edges + 1, edges + 1 + m, cmp);
        reverse(queries + 1, queries + 1 + q);
    
        for (int i = 1; i <= n; i++)
            lab[i] = -1, sz[i] = 1;

        int pt = 1;
        for (int i = 1; i <= q; i++)
        {
            auto [qw, qs, qid] = queries[i];
            auto [uu, vv, ww] = edges[pt];
            if (ww >= qw)
                for (; pt <= m; pt++)
                {
                    auto [u, v, w] = edges[pt];
                    if (w >= qw)
                        merge(u, v);
                    else
                        break;
                }

            ans[qid] = sz[get(qs)];
        }

        for (int i = 1; i <= q; i++)
            cout << ans[i] << '\n';
    }
} // namespace Sub3
 
 
signed main()
{
    // setIO();
    file;
    ios::sync_with_stdio(0); cin.tie(0);
 
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
 
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edges[i] = {u, v, w};
    }
 
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int type, fi, se;
        cin >> type >> fi >> se;
        Q[i] = {type, fi, se};
    }
 
    // if (Sub1::Check()) return Sub1::solve(), 0;
    // if (Sub2::Check()) return Sub2::solve(), 0;
    if (Sub3::Check()) return Sub3::solve(), 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void Sub1::solve()':
bridges.cpp:48:21: warning: unused variable 'b' [-Wunused-variable]
   48 |                 int b = fi, r = se;
      |                     ^
bridges.cpp: In function 'long long int Sub2::getR(long long int, long long int, long long int, long long int, long long int)':
bridges.cpp:179:33: warning: unused variable 'R' [-Wunused-variable]
  179 |                 int L = id * 2, R = id * 2 + 1, mid = (l + r) / 2;
      |                                 ^
bridges.cpp: In function 'void setIn(std::string)':
bridges.cpp:9:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void setOut(std::string)':
bridges.cpp:10:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:4:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:326:5: note: in expansion of macro 'file'
  326 |     file;
      |     ^~~~
bridges.cpp:4:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:326:5: note: in expansion of macro 'file'
  326 |     file;
      |     ^~~~

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