Submission #888356

#	Time	Username	Problem	Language	Result	Execution time	Memory
888356		rukashii	Bridges (APIO19_bridges)	C++17	13 / 100	130 ms	15304 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};

                // for (int i = 1; i <= m; i++)    
                // {
                //     auto [u, v, w] = edges[i];
                //     cout << u << ' ' << v << ' ' << w << '\n';
                // }
            }
            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


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

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:101:5: note: in expansion of macro 'file'
  101 |     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:101:5: note: in expansion of macro 'file'
  101 |     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