Submission #755358

#	Time	Username	Problem	Language	Result	Execution time	Memory
755358		fanwen	Bridges (APIO19_bridges)	C++17	13 / 100	3060 ms	9960 KiB

bridges

/**
 *      author : pham van sam 
 *      created : 10 June 2023 (Saturday)
 **/
#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

const int MAXN = 5e4 + 5;

struct Edge {
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
    int get(int x) { return u ^ v ^ x; }
};

int N, M, Q;
vector <int> adj[MAXN];

void process(void) {
    cin >> N >> M;
    vector <Edge> edges(M + 1);
    FOR(i, 1, M) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        adj[edges[i].u].push_back(i);
        adj[edges[i].v].push_back(i);
    }
    cin >> Q; while(Q--) {
        int type; cin >> type;
        if(type == 1) {
            int i, w; cin >> i >> w;
            edges[i].w = w;
        } else {
            int u, w; cin >> u >> w;
            vector <int> dd(N + 1);
            int ans = 0;
            function <void(int)> dfs = [&] (int u) {
                if(dd[u]) return;
                ans++; dd[u] = 1;
                for (auto i : adj[u]) if(edges[i].w >= w) {
                    dfs(edges[i].get(u));
                }
            };
            dfs(u);
            cout << ans << '\n';
        }
    }
}

signed main() {

    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    auto start_time = steady_clock::now();
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; ++i) {
        process();
        // cout << '\n';
    }

    auto end_time = steady_clock::now();

    cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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