oj.uz

Submission #747164

# Submission time Handle Problem Language Result Execution time Memory
747164 2023-05-23T19:09:08 Z Denkata Stranded Far From Home (BOI22_island) C++14
100 / 100
 299 ms 61816 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 2e5+3;
long long i,j,p,q,n,m,k;
vector <long long> s[maxn];
long long par[maxn],num[maxn],sum[maxn];
vector <long long> v[maxn];
vector <pair<long long,long long>> g[maxn];
pair <long long,long long> obh[maxn];
bool covered[maxn];
int Find(int p)
{
    if(par[p]==p)
        return p;
    return Find(par[p]);
}
void Union(int p,int q)
{
    p = Find(p);
    q = Find(q);
    if(p==q)
        return ;
    if(s[p].size()<s[q].size())
        swap(p,q);
    par[q] = p;
    sum[p] += sum[q];
    for(auto jj:s[q])
        s[p].push_back(jj);


    //s[q].clear();//reserve
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    vector <char> c(n);
    for(i=1;i<=n;i++)
    {
        cin>>num[i];
        obh[i] = {num[i],i};
    }
    sort(obh+1,obh+n+1);
    for(i=1;i<=m;i++)
    {
        cin>>p>>q;
        g[p].push_back({num[q],q});
        g[q].push_back({num[p],p});
    }
    for(i=1;i<=n;i++)
    {
        if(g[i].empty())
            continue;
        sort(g[i].begin(),g[i].end());
        for(auto j:g[i])
            v[i].push_back(j.second);
    }
    for(i=1;i<=n;i++)
    {
        par[i] = i;
        sum[i] = num[i];
        s[i].push_back(i);
    }
    for(i=1;i<=n;i++)
    {
        p = obh[i].second;
        covered[p] = true;
        k = Find(p);
        for(auto j:v[p])
        {
            int pp = Find(j);
            if(pp==k || num[j]>num[p])continue;
           // cout<<j<<endl;
            if(num[p]>sum[pp])
            {
                s[pp].clear();
            }
            Union(k,pp);
        }
    }
    p = Find(1);
    for(i=0;i<n;i++)
        c[i] = '0';
    for(auto i:s[p])
        c[i-1] = '1';
    for(auto i:c)
        cout<<i;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 8 ms 14676 KB Output is correct
5 Correct 9 ms 14840 KB Output is correct
6 Correct 9 ms 14772 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14692 KB Output is correct
9 Correct 9 ms 14768 KB Output is correct
10 Correct 9 ms 14824 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Correct 9 ms 14932 KB Output is correct
13 Correct 9 ms 14796 KB Output is correct
14 Correct 9 ms 14820 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 196 ms 49256 KB Output is correct
4 Correct 190 ms 48500 KB Output is correct
5 Correct 235 ms 55100 KB Output is correct
6 Correct 236 ms 56480 KB Output is correct
7 Correct 228 ms 56356 KB Output is correct
8 Correct 212 ms 52648 KB Output is correct
9 Correct 213 ms 61816 KB Output is correct
10 Correct 166 ms 49888 KB Output is correct
11 Correct 182 ms 53340 KB Output is correct
12 Correct 202 ms 51744 KB Output is correct
13 Correct 176 ms 50020 KB Output is correct
14 Correct 219 ms 50216 KB Output is correct
15 Correct 182 ms 51516 KB Output is correct
16 Correct 112 ms 50024 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14432 KB Output is correct
2 Correct 257 ms 52632 KB Output is correct
3 Correct 278 ms 56940 KB Output is correct
4 Correct 199 ms 51584 KB Output is correct
5 Correct 232 ms 50324 KB Output is correct
6 Correct 280 ms 56764 KB Output is correct
7 Correct 195 ms 51592 KB Output is correct
8 Correct 192 ms 51596 KB Output is correct
9 Correct 119 ms 50100 KB Output is correct
10 Correct 188 ms 49860 KB Output is correct
11 Correct 250 ms 50764 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 265 ms 50012 KB Output is correct
3 Correct 273 ms 54592 KB Output is correct
4 Correct 276 ms 56840 KB Output is correct
5 Correct 270 ms 58700 KB Output is correct
6 Correct 247 ms 54584 KB Output is correct
7 Correct 187 ms 54320 KB Output is correct
8 Correct 126 ms 53336 KB Output is correct
9 Correct 161 ms 40336 KB Output is correct
10 Correct 257 ms 58764 KB Output is correct
11 Correct 214 ms 50748 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 8 ms 14676 KB Output is correct
5 Correct 9 ms 14840 KB Output is correct
6 Correct 9 ms 14772 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14692 KB Output is correct
9 Correct 9 ms 14768 KB Output is correct
10 Correct 9 ms 14824 KB Output is correct
11 Correct 9 ms 14804 KB Output is correct
12 Correct 9 ms 14932 KB Output is correct
13 Correct 9 ms 14796 KB Output is correct
14 Correct 9 ms 14820 KB Output is correct
15 Correct 8 ms 14420 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Correct 196 ms 49256 KB Output is correct
18 Correct 190 ms 48500 KB Output is correct
19 Correct 235 ms 55100 KB Output is correct
20 Correct 236 ms 56480 KB Output is correct
21 Correct 228 ms 56356 KB Output is correct
22 Correct 212 ms 52648 KB Output is correct
23 Correct 213 ms 61816 KB Output is correct
24 Correct 166 ms 49888 KB Output is correct
25 Correct 182 ms 53340 KB Output is correct
26 Correct 202 ms 51744 KB Output is correct
27 Correct 176 ms 50020 KB Output is correct
28 Correct 219 ms 50216 KB Output is correct
29 Correct 182 ms 51516 KB Output is correct
30 Correct 112 ms 50024 KB Output is correct
31 Correct 8 ms 14432 KB Output is correct
32 Correct 257 ms 52632 KB Output is correct
33 Correct 278 ms 56940 KB Output is correct
34 Correct 199 ms 51584 KB Output is correct
35 Correct 232 ms 50324 KB Output is correct
36 Correct 280 ms 56764 KB Output is correct
37 Correct 195 ms 51592 KB Output is correct
38 Correct 192 ms 51596 KB Output is correct
39 Correct 119 ms 50100 KB Output is correct
40 Correct 188 ms 49860 KB Output is correct
41 Correct 250 ms 50764 KB Output is correct
42 Correct 8 ms 14420 KB Output is correct
43 Correct 265 ms 50012 KB Output is correct
44 Correct 273 ms 54592 KB Output is correct
45 Correct 276 ms 56840 KB Output is correct
46 Correct 270 ms 58700 KB Output is correct
47 Correct 247 ms 54584 KB Output is correct
48 Correct 187 ms 54320 KB Output is correct
49 Correct 126 ms 53336 KB Output is correct
50 Correct 161 ms 40336 KB Output is correct
51 Correct 257 ms 58764 KB Output is correct
52 Correct 214 ms 50748 KB Output is correct
53 Correct 8 ms 14420 KB Output is correct
54 Correct 8 ms 14392 KB Output is correct
55 Correct 8 ms 14428 KB Output is correct
56 Correct 8 ms 14728 KB Output is correct
57 Correct 9 ms 14824 KB Output is correct
58 Correct 8 ms 14676 KB Output is correct
59 Correct 8 ms 14676 KB Output is correct
60 Correct 9 ms 14688 KB Output is correct
61 Correct 9 ms 14768 KB Output is correct
62 Correct 9 ms 14860 KB Output is correct
63 Correct 9 ms 14828 KB Output is correct
64 Correct 9 ms 14820 KB Output is correct
65 Correct 8 ms 14804 KB Output is correct
66 Correct 10 ms 14832 KB Output is correct
67 Correct 200 ms 53200 KB Output is correct
68 Correct 196 ms 51272 KB Output is correct
69 Correct 217 ms 54928 KB Output is correct
70 Correct 240 ms 56632 KB Output is correct
71 Correct 231 ms 56456 KB Output is correct
72 Correct 195 ms 52632 KB Output is correct
73 Correct 213 ms 61816 KB Output is correct
74 Correct 158 ms 49872 KB Output is correct
75 Correct 174 ms 53276 KB Output is correct
76 Correct 193 ms 51656 KB Output is correct
77 Correct 174 ms 49964 KB Output is correct
78 Correct 200 ms 50248 KB Output is correct
79 Correct 176 ms 51552 KB Output is correct
80 Correct 117 ms 49992 KB Output is correct
81 Correct 264 ms 56648 KB Output is correct
82 Correct 283 ms 57020 KB Output is correct
83 Correct 203 ms 51612 KB Output is correct
84 Correct 204 ms 50212 KB Output is correct
85 Correct 266 ms 56784 KB Output is correct
86 Correct 202 ms 51520 KB Output is correct
87 Correct 189 ms 51524 KB Output is correct
88 Correct 181 ms 49888 KB Output is correct
89 Correct 220 ms 50736 KB Output is correct
90 Correct 277 ms 53828 KB Output is correct
91 Correct 265 ms 54612 KB Output is correct
92 Correct 291 ms 56684 KB Output is correct
93 Correct 294 ms 58684 KB Output is correct
94 Correct 262 ms 54560 KB Output is correct
95 Correct 175 ms 54260 KB Output is correct
96 Correct 117 ms 53148 KB Output is correct
97 Correct 172 ms 40300 KB Output is correct
98 Correct 254 ms 58884 KB Output is correct
99 Correct 216 ms 50660 KB Output is correct
100 Correct 67 ms 28952 KB Output is correct
101 Correct 288 ms 55248 KB Output is correct
102 Correct 245 ms 49532 KB Output is correct
103 Correct 234 ms 48792 KB Output is correct
104 Correct 299 ms 52820 KB Output is correct