Submission #1095167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095167		ro9669	Bridges (APIO19_bridges)	C++17	13 / 100	3078 ms	4016 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(1e5)+7;
const int block_size = 320;

int n , m , q;
pair<int , ii> edge[maxN] , query[maxN];
int id[maxN] , fa[maxN];
vector<pair<ii , ii>> event;

int root(int x){
    if (fa[x] < 0) return x; else return root(fa[x]);
}

void unite(int u , int v , int t){
    u = root(u);
    v = root(v);
    if (u == v) return;
    if (t == 1){
        event.push_back({{u , fa[u]} , {v , fa[v]}});
    }
    if (-fa[u] < -fa[v]) swap(u , v);
    fa[u] += fa[v];
    fa[v] = u;
}

void unite(int id , int t){
    unite(edge[id].se.fi , edge[id].se.se , t);
}

void rollback(){
    while (event.empty() == 0){
        auto it = event.back(); event.pop_back();
        fa[it.fi.fi] = it.fi.se;
        fa[it.se.fi] = it.se.se;
    }
}

void solve(){
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        edge[i] = {w , {u , v}};
    }
    cin >> q;
    for (int i = 1 ; i <= q ; i++){
        int t , x , y;
        cin >> t >> x >> y;
        if (t == 1){
            edge[x].fi = y;
        }
        else{
            for (int i = 1 ; i <= n ; i++) fa[i] = -1;
            for (int j = 1 ; j <= m ; j++){
                if (edge[j].fi >= y){
                    unite(j , 0);
                }
            }
            cout << -fa[root(x)] << "\n";
        }
    }
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".ANS" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(name".ANS" , "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