oj.uz

답안 #934046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934046 2024-02-26T17:59:25 Z Lemser 다리 (APIO19_bridges) C++14
14 / 100
 84 ms 16688 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define fore(i,l,r) for(int i = l; i < r;i++)
#define forex(i,r,l) for(int i = r; i>= l;i--)
#define fo(i,n) fore(i,0,n)
#define ffo(i,n) forex(i,n-1,0)
#define lsb(x) x&(-x)
using namespace std;
using ii = pair<int,int>;using ll = long long; using ull = unsigned long long;
using vi = vector<int>;
const int N = 1e5+7;
int res[N];
vector<ii> graph[N];
struct evento{
    int peso, a,b,i;
};
vector<evento> eventos;
bool ord(evento a, evento b){
    if(a.peso == b.peso)return a.b > b.b; // las updates primero 
    return a.peso > b.peso;
}
struct dsu{
    vi pa,nh; int gru;
    dsu(int n){
        pa.resize(n+1);
        nh.resize(n+1);
        gru = n;
        fo(i,n+1){
            pa[i] = i;nh[i] = 1;
        }
    }
    int find(int i ){
        if(pa[i] == i) return i;
        return pa[i] = find(pa[i]);
    }
    void unite(int a, int b ){
        a = find(a); b = find(b);
        if(a == b)return;
        if(nh[a] < nh[b])swap(a,b);
        pa[b]=a;
        nh[a]+=nh[b];gru--;
    }
    int tam(int a ){
        return nh[find(a)];
    }
};
struct query{
    int op,a,b;
};
int main(){cin.tie(0)->sync_with_stdio(0);
    int n,m; cin >> n >> m;
    fo(i,m){
        int a,b,w; cin >> a >> b >> w;
        eventos.pb({w,a,b,i});
        graph[a].pb({b,w});
        graph[b].pb({a,w});
    }
    int q; cin >> q;
    int con = 0;
    vector<query> queries;
    fo(i,q){
        int op; cin >> op;
        if(op==2) con++;
        int nodo, peso;
        cin >> nodo >> peso;
        queries.pb({op,nodo,peso});
        eventos.pb({peso, nodo,-1,i});
    }
    if(con == q){// No hay updates
        sort(all(eventos), ord);
        dsu ami(n);
        for(auto e : eventos){
            if(e.b == -1){
                res[e.i] = ami.tam(e.a);
            }else{
                ami.unite(e.a,e.b);
            }
        }
        fo(i,q)cout << res[i] << endl;
    }else if (m==n-1){

    }else{

    }
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 12732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 10684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 12572 KB Output is correct
2 Correct 37 ms 7524 KB Output is correct
3 Correct 37 ms 8568 KB Output is correct
4 Correct 31 ms 8900 KB Output is correct
5 Correct 68 ms 15288 KB Output is correct
6 Correct 75 ms 16688 KB Output is correct
7 Correct 64 ms 14776 KB Output is correct
8 Correct 55 ms 13508 KB Output is correct
9 Correct 57 ms 14532 KB Output is correct
10 Correct 59 ms 14756 KB Output is correct
11 Correct 70 ms 14844 KB Output is correct
12 Correct 75 ms 15184 KB Output is correct
13 Correct 67 ms 14832 KB Output is correct
14 Correct 64 ms 15540 KB Output is correct
15 Correct 66 ms 14980 KB Output is correct
16 Correct 78 ms 15720 KB Output is correct
17 Correct 79 ms 15796 KB Output is correct
18 Correct 84 ms 16000 KB Output is correct
19 Correct 75 ms 15848 KB Output is correct
20 Correct 74 ms 15892 KB Output is correct
21 Correct 70 ms 16536 KB Output is correct
22 Correct 76 ms 15544 KB Output is correct
23 Correct 58 ms 14780 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 12732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -