oj.uz

Submission #573285

# Submission time Handle Problem Language Result Execution time Memory
573285 2022-06-06T11:09:32 Z AmirElarbi Stranded Far From Home (BOI22_island) C++14
10 / 100
 706 ms 524288 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9+7
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e4+7;
const int nax = 4e5+5;
typedef complex<int> Point;
#define X real()
#define Y imag()
vii s;
vi adj[nax], nds[nax];
ll ans[nax];
ll p[nax], sz[nax];
int find_set(int v) {
    if (v == p[v])
        return v;
    return p[v] = find_set(p[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b){
        //if(nds[b].size() > nds[a].size()) swap(nds[a],nds[b]);
        for(auto x : nds[b]) nds[a].pb(x);
        p[b] = a;
        sz[a] += sz[b];
    }
}
int main(){
    optimise;
    int n,m;
    cin >>n >> m;
    for (int i = 0; i < n; ++i)
    {
        int val;
        cin >> val;
        sz[i] = val;
        p[i] = i;
        nds[i].pb(i);
        s.pb({val,i});
    }
    for (int i = 0; i < m; ++i)
    {
        int a,b;
        cin >> a >> b;
        a--,b--;
        if(mp(sz[a],a) < mp(sz[b],b) ) swap(a,b);
        adj[a].pb(b);
    }
    sort(s.begin(), s.end());
    for (int i = 0; i < n; ++i)
    {
        int u = find_set(s[i].se);
        for(auto x : adj[u]){
            x = find_set(x);
            if(sz[u] > sz[x]) nds[x].clear();
        }
        for(auto x : adj[u]) union_sets(x,u);  
    }
    for(auto x: nds[find_set(0)])
        ans[x] = 1;
    for (int i = 0; i < n; ++i)
    {
        cout << ans[i];
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 11 ms 19016 KB Output is correct
3 Correct 12 ms 19028 KB Output is correct
4 Correct 13 ms 19668 KB Output is correct
5 Correct 12 ms 19412 KB Output is correct
6 Correct 12 ms 20052 KB Output is correct
7 Correct 12 ms 19664 KB Output is correct
8 Correct 11 ms 19540 KB Output is correct
9 Correct 11 ms 19272 KB Output is correct
10 Correct 11 ms 19284 KB Output is correct
11 Correct 12 ms 19304 KB Output is correct
12 Correct 11 ms 19284 KB Output is correct
13 Correct 11 ms 19284 KB Output is correct
14 Correct 13 ms 19388 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19132 KB Output is correct
2 Correct 11 ms 19028 KB Output is correct
3 Runtime error 630 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 194 ms 42772 KB Output is correct
3 Correct 213 ms 43340 KB Output is correct
4 Correct 180 ms 40668 KB Output is correct
5 Correct 123 ms 38032 KB Output is correct
6 Correct 209 ms 43508 KB Output is correct
7 Correct 139 ms 39912 KB Output is correct
8 Correct 148 ms 39896 KB Output is correct
9 Correct 90 ms 39684 KB Output is correct
10 Runtime error 616 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Runtime error 706 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 11 ms 19016 KB Output is correct
3 Correct 12 ms 19028 KB Output is correct
4 Correct 13 ms 19668 KB Output is correct
5 Correct 12 ms 19412 KB Output is correct
6 Correct 12 ms 20052 KB Output is correct
7 Correct 12 ms 19664 KB Output is correct
8 Correct 11 ms 19540 KB Output is correct
9 Correct 11 ms 19272 KB Output is correct
10 Correct 11 ms 19284 KB Output is correct
11 Correct 12 ms 19304 KB Output is correct
12 Correct 11 ms 19284 KB Output is correct
13 Correct 11 ms 19284 KB Output is correct
14 Correct 13 ms 19388 KB Output is correct
15 Correct 11 ms 19132 KB Output is correct
16 Correct 11 ms 19028 KB Output is correct
17 Runtime error 630 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -