oj.uz

Submission #757737

# Submission time Handle Problem Language Result Execution time Memory
757737 2023-06-13T17:05:07 Z karrigan Stranded Far From Home (BOI22_island) C++14
100 / 100
 423 ms 78564 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
using pil=pair<int,long long>;
using pll=pair<long long,long long>;
const int maxn=2e5+9;
int lab[maxn*2];
vector<int>a[maxn*2];
int findset(int u){
if (lab[u]==u)return u;
return lab[u]=findset(lab[u]);
}
int nnode=0;
int n,m;
int mx[maxn*2];
void unite(int u,int v,int w){
u=findset(u),v=findset(v);
if (u==v)return;
nnode++;
lab[nnode]=nnode;
a[nnode].pb(u);
a[nnode].pb(v);
mx[nnode]=w;
lab[u]=nnode;
lab[v]=nnode;
}
int b[maxn];
int d[maxn];
struct edg{
    int u,v;
    bool operator <(const edg &p)const {
    return max(b[u],b[v])<max(b[p.u],b[p.v]);
    }
}c[maxn];
long long sub[maxn*2];
int st[maxn*2][21];
void dfs(int u){
for (auto v:a[u]){
    st[v][0]=u;
    for1(j,1,20){
    st[v][j]=st[st[v][j-1]][j-1];
    }
    dfs(v);
    sub[u]+=sub[v];
}
}
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("usaco.INP","r",stdin);
    //freopen("usaco.OUT","w",stdout);
    cin>>n>>m;
    for1(i,1,n){
    cin>>b[i];
    lab[i]=i;
    d[i]=b[i];
    mx[i]=b[i];
    sub[i]+=b[i];
    }
    sort(d+1,d+1+n);
    for1(i,1,m){
    cin>>c[i].u>>c[i].v;
    }
    sort(c+1,c+1+m);
    nnode=n;
    for1(i,1,m){
    unite(c[i].u,c[i].v,max(b[c[i].u],b[c[i].v]));
    }
    dfs(nnode);
    for1(i,1,n){
    long long nn=b[i];
    bool fl=false;
    while (true){
    //cerr<<nn<<'\n';
    int id=upper_bound(d+1,d+1+n,nn)-d;
    if (id==1+n){
        fl=true;
        break;
    }
    int kaka=i;
    for2(j,20,0){
    if (st[kaka][j]==0)continue;
    if (mx[st[kaka][j]]<=nn){
        kaka=st[kaka][j];
    }
    }
    //cout<<sub[kaka]<<'\n';
    long long newsum=sub[kaka];
    int id2=upper_bound(d+1,d+1+n,newsum)-d;
    if (id==id2){
        break;
    }
    nn=newsum;
    }
    cout<<fl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 8 ms 10188 KB Output is correct
5 Correct 7 ms 10196 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 8 ms 10196 KB Output is correct
8 Correct 9 ms 10068 KB Output is correct
9 Correct 7 ms 10324 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct
11 Correct 8 ms 10196 KB Output is correct
12 Correct 8 ms 10256 KB Output is correct
13 Correct 7 ms 10220 KB Output is correct
14 Correct 7 ms 10196 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9652 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 274 ms 70940 KB Output is correct
4 Correct 233 ms 61460 KB Output is correct
5 Correct 307 ms 61168 KB Output is correct
6 Correct 318 ms 62820 KB Output is correct
7 Correct 336 ms 62868 KB Output is correct
8 Correct 299 ms 62924 KB Output is correct
9 Correct 209 ms 62756 KB Output is correct
10 Correct 267 ms 77620 KB Output is correct
11 Correct 207 ms 77464 KB Output is correct
12 Correct 288 ms 61360 KB Output is correct
13 Correct 220 ms 61384 KB Output is correct
14 Correct 225 ms 61544 KB Output is correct
15 Correct 230 ms 78460 KB Output is correct
16 Correct 208 ms 77200 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 353 ms 62572 KB Output is correct
3 Correct 328 ms 62916 KB Output is correct
4 Correct 231 ms 62868 KB Output is correct
5 Correct 217 ms 61328 KB Output is correct
6 Correct 318 ms 63000 KB Output is correct
7 Correct 244 ms 78452 KB Output is correct
8 Correct 246 ms 78540 KB Output is correct
9 Correct 208 ms 77320 KB Output is correct
10 Correct 241 ms 62240 KB Output is correct
11 Correct 251 ms 61428 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 333 ms 63736 KB Output is correct
3 Correct 324 ms 62864 KB Output is correct
4 Correct 312 ms 63108 KB Output is correct
5 Correct 289 ms 62920 KB Output is correct
6 Correct 268 ms 62124 KB Output is correct
7 Correct 252 ms 78380 KB Output is correct
8 Correct 196 ms 69592 KB Output is correct
9 Correct 190 ms 38120 KB Output is correct
10 Correct 264 ms 61460 KB Output is correct
11 Correct 261 ms 61352 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 8 ms 10188 KB Output is correct
5 Correct 7 ms 10196 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 8 ms 10196 KB Output is correct
8 Correct 9 ms 10068 KB Output is correct
9 Correct 7 ms 10324 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct
11 Correct 8 ms 10196 KB Output is correct
12 Correct 8 ms 10256 KB Output is correct
13 Correct 7 ms 10220 KB Output is correct
14 Correct 7 ms 10196 KB Output is correct
15 Correct 5 ms 9652 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 274 ms 70940 KB Output is correct
18 Correct 233 ms 61460 KB Output is correct
19 Correct 307 ms 61168 KB Output is correct
20 Correct 318 ms 62820 KB Output is correct
21 Correct 336 ms 62868 KB Output is correct
22 Correct 299 ms 62924 KB Output is correct
23 Correct 209 ms 62756 KB Output is correct
24 Correct 267 ms 77620 KB Output is correct
25 Correct 207 ms 77464 KB Output is correct
26 Correct 288 ms 61360 KB Output is correct
27 Correct 220 ms 61384 KB Output is correct
28 Correct 225 ms 61544 KB Output is correct
29 Correct 230 ms 78460 KB Output is correct
30 Correct 208 ms 77200 KB Output is correct
31 Correct 6 ms 9684 KB Output is correct
32 Correct 353 ms 62572 KB Output is correct
33 Correct 328 ms 62916 KB Output is correct
34 Correct 231 ms 62868 KB Output is correct
35 Correct 217 ms 61328 KB Output is correct
36 Correct 318 ms 63000 KB Output is correct
37 Correct 244 ms 78452 KB Output is correct
38 Correct 246 ms 78540 KB Output is correct
39 Correct 208 ms 77320 KB Output is correct
40 Correct 241 ms 62240 KB Output is correct
41 Correct 251 ms 61428 KB Output is correct
42 Correct 6 ms 9684 KB Output is correct
43 Correct 333 ms 63736 KB Output is correct
44 Correct 324 ms 62864 KB Output is correct
45 Correct 312 ms 63108 KB Output is correct
46 Correct 289 ms 62920 KB Output is correct
47 Correct 268 ms 62124 KB Output is correct
48 Correct 252 ms 78380 KB Output is correct
49 Correct 196 ms 69592 KB Output is correct
50 Correct 190 ms 38120 KB Output is correct
51 Correct 264 ms 61460 KB Output is correct
52 Correct 261 ms 61352 KB Output is correct
53 Correct 5 ms 9684 KB Output is correct
54 Correct 5 ms 9684 KB Output is correct
55 Correct 6 ms 9684 KB Output is correct
56 Correct 7 ms 10216 KB Output is correct
57 Correct 8 ms 10196 KB Output is correct
58 Correct 7 ms 10196 KB Output is correct
59 Correct 7 ms 10196 KB Output is correct
60 Correct 7 ms 10068 KB Output is correct
61 Correct 7 ms 10252 KB Output is correct
62 Correct 8 ms 10196 KB Output is correct
63 Correct 8 ms 10196 KB Output is correct
64 Correct 7 ms 10196 KB Output is correct
65 Correct 7 ms 10196 KB Output is correct
66 Correct 7 ms 10208 KB Output is correct
67 Correct 263 ms 70948 KB Output is correct
68 Correct 228 ms 61500 KB Output is correct
69 Correct 313 ms 61184 KB Output is correct
70 Correct 331 ms 62668 KB Output is correct
71 Correct 326 ms 63044 KB Output is correct
72 Correct 299 ms 62916 KB Output is correct
73 Correct 204 ms 62708 KB Output is correct
74 Correct 271 ms 77552 KB Output is correct
75 Correct 202 ms 77496 KB Output is correct
76 Correct 287 ms 61400 KB Output is correct
77 Correct 228 ms 61284 KB Output is correct
78 Correct 217 ms 61516 KB Output is correct
79 Correct 232 ms 78428 KB Output is correct
80 Correct 207 ms 77212 KB Output is correct
81 Correct 344 ms 62540 KB Output is correct
82 Correct 348 ms 62920 KB Output is correct
83 Correct 227 ms 62844 KB Output is correct
84 Correct 238 ms 61468 KB Output is correct
85 Correct 353 ms 63008 KB Output is correct
86 Correct 249 ms 78544 KB Output is correct
87 Correct 245 ms 78540 KB Output is correct
88 Correct 249 ms 62176 KB Output is correct
89 Correct 267 ms 61332 KB Output is correct
90 Correct 335 ms 63784 KB Output is correct
91 Correct 322 ms 62896 KB Output is correct
92 Correct 317 ms 62964 KB Output is correct
93 Correct 263 ms 62920 KB Output is correct
94 Correct 259 ms 62232 KB Output is correct
95 Correct 276 ms 78564 KB Output is correct
96 Correct 200 ms 69616 KB Output is correct
97 Correct 191 ms 38036 KB Output is correct
98 Correct 273 ms 61316 KB Output is correct
99 Correct 263 ms 61352 KB Output is correct
100 Correct 61 ms 14416 KB Output is correct
101 Correct 404 ms 62964 KB Output is correct
102 Correct 220 ms 55040 KB Output is correct
103 Correct 353 ms 60260 KB Output is correct
104 Correct 423 ms 64372 KB Output is correct