Submission #888383

#	Time	Username	Problem	Language	Result	Execution time	Memory
888383		rukashii	Bridges (APIO19_bridges)	C++17	13 / 100	118 ms	13140 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 u, int v, int val)
    {
        if (r < u || v < l)
            assert(0);
        if (l == r)
            return l;
        
        int mid = (l + r) / 2;
        if (tree[id * 2 + 1] < val && (!(v < (mid + 1) || r < u)))
            return getL(id * 2 + 1, mid + 1, r, u, v, val);
        else
            return getL(id * 2, l, mid, u, v, val);
    }

    int getR(int id, int l, int r, int u, int v, int val)
    {
        if (r < u || v < l)
            assert(0);
        
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        
        if (tree[id * 2] < val && (!(l > v || mid < u)))
            return getR(id * 2, l, mid, u, v, val);
        else
            return getR(id * 2 + 1, mid + 1, r, u, v, 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 = getL(1, 1, n, 1, fi - 1, se);
                }
                if (fi < n)
                {
                    Rbor = getR(1, 1, n, fi, n, se);
                }
 
                cout << Rbor - Lbor + 1 << '\n';
            }
        }
    }
} // namespace Sub2


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;
}

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 '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:199:5: note: in expansion of macro 'file'
  199 |     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:199:5: note: in expansion of macro 'file'
  199 |     file;
      |     ^~~~

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