Submission #888392

#	Time	Username	Problem	Language	Result	Execution time	Memory
888392		rukashii	Bridges (APIO19_bridges)	C++17	13 / 100	115 ms	13368 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)
        {
            if (a[l] >= val)
                l--;
            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)
        {
            if (a[l] >= val)
                l++;
            return l;
        }
        int mid = (l + r) / 2;

        // cout << l << ' ' << r << ' ' << tree[id * 2] << ' ' << val << '\n';
        
        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, m, 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, m, fi, se);
            }
            else
            {
                int Lbor = fi - 1, Rbor = fi;
                if (fi > 1)
                {
                    Lbor = getL(1, 1, m, 1, fi - 1, se);
                }
                if (fi < n)
                {
                    Rbor = getR(1, 1, m, fi, m, se);
                }

                // cout << Lbor << ' ' << Rbor << '\n';
                cout << Rbor - Lbor << '\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:209:5: note: in expansion of macro 'file'
  209 |     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:209:5: note: in expansion of macro 'file'
  209 |     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