oj.uz

답안 #434708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
434708 2021-06-21T15:18:52 Z Mounir 다리 (APIO19_bridges) C++14
14 / 100
 451 ms 14216 KB 
#include <bits/stdc++.h>
#define chmax(x, v) x = max(x, v)
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define int long long
using namespace std;
     
const int N = 1e6;
 
struct Arete {
    int noeud, voisin, poids;
 
    bool operator < (const Arete &autre) const {
        if (poids != autre.poids)
            return poids > autre.poids;
        if (voisin != autre.voisin)
            return voisin > autre.voisin;
        return noeud < autre.noeud;
    }
};
 
int ens[N], taille[N];
 
int getEns(int noeud){
    if (ens[noeud] != noeud)
        ens[noeud] = getEns(ens[noeud]);
    return ens[noeud];
}
 
int ans[N];
 
     
signed main(){
    int nNoeuds, nAretes; cin >> nNoeuds >> nAretes;
    vector<Arete> aretes(nAretes);
    for (Arete& arete : aretes)
        cin >> arete.noeud >> arete.voisin >> arete.poids;
    for (int noeud = 1; noeud <= nNoeuds; ++noeud){
        ens[noeud] = noeud;
        taille[noeud] = 1;
    }
 
    int nReqs; cin >> nReqs;
    for (int iReq = 0; iReq < nReqs; ++iReq){
        int typeReq, noeud, poids; cin >> typeReq >> noeud >> poids;
        aretes.pb({noeud, -iReq, poids});
    }
 
    sort(all(aretes));
    for (Arete& arete : aretes){
        if (arete.voisin > 0){
            arete.noeud = getEns(arete.noeud), arete.voisin = getEns(arete.voisin);
            if (arete.noeud != arete.voisin){
                ens[arete.noeud] = arete.voisin;
                taille[arete.voisin] += taille[arete.noeud];
            }
        }
        else {
            arete.voisin = -arete.voisin;
            ans[arete.voisin] = taille[getEns(arete.noeud)];
        }
    }
 
    for (int iReq = 0; iReq < nReqs; ++iReq)
        cout << ans[iReq] << endl;
    return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 384 ms 7028 KB Output is correct
2 Correct 255 ms 5188 KB Output is correct
3 Correct 128 ms 6848 KB Output is correct
4 Correct 136 ms 6852 KB Output is correct
5 Correct 342 ms 9328 KB Output is correct
6 Correct 394 ms 10772 KB Output is correct
7 Correct 336 ms 9368 KB Output is correct
8 Correct 316 ms 8180 KB Output is correct
9 Correct 323 ms 8496 KB Output is correct
10 Correct 313 ms 8184 KB Output is correct
11 Correct 354 ms 10976 KB Output is correct
12 Correct 353 ms 11156 KB Output is correct
13 Correct 347 ms 10924 KB Output is correct
14 Correct 337 ms 9416 KB Output is correct
15 Correct 344 ms 9460 KB Output is correct
16 Correct 414 ms 14096 KB Output is correct
17 Correct 451 ms 14000 KB Output is correct
18 Correct 382 ms 14216 KB Output is correct
19 Correct 404 ms 14120 KB Output is correct
20 Correct 348 ms 11936 KB Output is correct
21 Correct 349 ms 11936 KB Output is correct
22 Correct 387 ms 13464 KB Output is correct
23 Correct 338 ms 10452 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

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