oj.uz

답안 #869478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869478 2023-11-04T12:18:47 Z lolismek Stranded Far From Home (BOI22_island) C++14
25 / 100
 230 ms 36612 KB 
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>

#define int long long
#define pii pair <int, int>

using namespace std;

//ifstream fin("input.in");
//ofstream fout("output.out");

#define fin cin
#define fout cout

const int NMAX = 2e5;

int v[NMAX + 1];
vector <int> adj[NMAX + 1];

int par[NMAX + 1];
int sum[NMAX + 1];

bool bad[NMAX + 1];
int Find(int x){
    if(x == par[x]){
        return x;
    }
    int y = Find(par[x]); // ?
    bad[x] |= bad[par[x]];
    par[x] = y;
    return par[x];
}

void Join(int x, int y){
    x = Find(x);
    y = Find(y);

    if(v[x] < v[y]){
        swap(x, y);
    }

    if(v[x] > sum[y]){
        bad[y] = 1;
    }

    par[y] = x;
    sum[x] += sum[y];
}

bool ins[NMAX + 1];

void Insert(int x){
    ins[x] = true;
    for(int vec : adj[x]){
        if(ins[vec]){
            Join(vec, x);
        }
    }
}

vector <int> inds[NMAX + 1];

pii e[NMAX + 1];

signed main(){

    int n, m;
    cin >> n >> m;

    vector <int> vals;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        par[i] = i;
        sum[i] = v[i];
        vals.push_back(v[i]);
    }

    vector <pii> aux;
    for(int i = 1; i <= m; i++){
        int a, b;
        fin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        e[i] = {a, b};
        aux.push_back({max(v[a], v[b]), i});
    }

    sort(aux.begin(), aux.end());

    for(pii x : aux){
        Join(e[x.second].first, e[x.second].second);
    }

    for(int i = 1; i <= n; i++){
        Find(i);
        cout << !bad[i];
    }
    cout << '\n';

    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14804 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Incorrect 4 ms 14940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 205 ms 30532 KB Output is correct
4 Correct 175 ms 30656 KB Output is correct
5 Correct 230 ms 33884 KB Output is correct
6 Correct 203 ms 34492 KB Output is correct
7 Correct 210 ms 34492 KB Output is correct
8 Correct 201 ms 35332 KB Output is correct
9 Correct 204 ms 35772 KB Output is correct
10 Correct 169 ms 34500 KB Output is correct
11 Correct 158 ms 36612 KB Output is correct
12 Correct 170 ms 33724 KB Output is correct
13 Correct 161 ms 31928 KB Output is correct
14 Correct 179 ms 32952 KB Output is correct
15 Correct 197 ms 33752 KB Output is correct
16 Correct 156 ms 32676 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 15092 KB Output is correct
2 Correct 204 ms 29752 KB Output is correct
3 Correct 209 ms 33468 KB Output is correct
4 Correct 190 ms 34492 KB Output is correct
5 Correct 165 ms 32960 KB Output is correct
6 Correct 206 ms 33472 KB Output is correct
7 Correct 215 ms 34752 KB Output is correct
8 Correct 217 ms 33536 KB Output is correct
9 Correct 153 ms 32700 KB Output is correct
10 Correct 210 ms 32956 KB Output is correct
11 Correct 193 ms 32184 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Incorrect 211 ms 30184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14804 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Incorrect 4 ms 14940 KB Output isn't correct
5 Halted 0 ms 0 KB -