Submission #1032840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032840		KasymK	Bridges (APIO19_bridges)	C++17	14 / 100	66 ms	8992 KiB

bridges

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int MOD = 1e9+7;
const int N = 1e5+5;
const ll INF = 1e18+1;

vector<int> p, sz;
 
int fnd(int x) {
    return p[x] = (x == p[x] ? x : fnd(p[x]));
}
 
void uni(int x, int y) {
    x = fnd(x); y = fnd(y);
 
    if (x == y) return;
 
    p[x] = y;
    sz[y] += sz[x];
}
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<pair<pii, pii>> v;
    while (m--) {
        int x, y, d;
        scanf("%d%d%d", &x, &y, &d);
        v.pb({{d, INT_MAX}, {--x, --y}});
    }
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        int t, s, w;
        scanf("%d%d%d", &t, &s, &w);
        v.pb({{w, i}, {--s, 0}});
    }
 
    p.assign(n, 0);
    sz.assign(n, 1);
    iota(p.begin(), p.end(), 0); // fill inside
    sort(all(v));
    reverse(all(v));
 
    vector<int> ans(q);
    for (auto i : v) {
        if (i.ff.ss == INT_MAX)
        	uni(i.ss.ff, i.ss.ss);
        else
        	ans[i.ff.ss] = sz[fnd(i.ss.ff)];
    }
 
    for (auto i : ans)
    	printf("%d\n", i);
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d%d%d", &x, &y, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
bridges.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d%d%d", &t, &s, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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