oj.uz

Submission #580065

# Submission time Handle Problem Language Result Execution time Memory
580065 2022-06-20T14:21:37 Z jasmin Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 23184 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

struct graph{
    int n;
    vector<vector<int> > adi;
    vector<int> chef;
    vector<int> s;
    vector<int> time;

    graph(int a, vector<int>& size){
        n=a;
        adi.resize(n);
        chef.resize(n);
        iota(chef.begin(), chef.end(), 0);
        s.resize(n);
        for(int i=0; i<n; i++){
            s[i]=size[i];
        }
        time.resize(n);
    }

    int find(int a){
        if(chef[a]==a) return a;
        return chef[a]=find(chef[a]);
    }
    bool unite(int a, int b){
        if(find(a)==find(b)){
            return false;
        }
        s[find(a)]+=s[find(b)];
        chef[find(b)]=find(a);
        return true;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> size(n);
    vector<pair<int,int> > r(n);
    for(int i=0; i<n; i++){
        cin >> size[i];
        r[i]={size[i], i};
    }
    graph g(n, size);
    sort(r.begin(), r.end());
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        g.adi[a-1].push_back(b-1);
        g.adi[b-1].push_back(a-1);
    }

    vector<int> tin(n);
    vector<bool> ans(n, true);
    for(int i=0; i<n; i++){

        int v=r[i].second;
        tin[v]=i;
        for(auto u: g.adi[v]){
            if(size[u]<=size[v]){

                if(g.s[g.find(u)]<size[v]){
                    g.time[g.find(u)]=i;
                    for(int j=0; j<n; j++){
                        if(g.find(j)==g.find(u)){
                            ans[j]=false;
                        }
                    }
                }
                g.unite(u, v);
            }
        }
    }

    for(auto e: ans){
        cout << e;
    }
    cout << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 7 ms 524 KB Output is correct
5 Correct 9 ms 524 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 8 ms 540 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 7 ms 468 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 1088 ms 23184 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1087 ms 22028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1089 ms 23176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 7 ms 524 KB Output is correct
5 Correct 9 ms 524 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 8 ms 540 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 1088 ms 23184 KB Time limit exceeded
18 Halted 0 ms 0 KB -