oj.uz

Submission #1016061

# Submission time Handle Problem Language Result Execution time Memory
1016061 2024-07-07T10:56:03 Z bachhoangxuan Road Service 2 (JOI24_ho_t5) C++17
48 / 100
 476 ms 123232 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
const int maxl = 25;
const int inf = 1e9;
#define pii array<int,2>

int par[2*maxn],lt[2*maxn],rt[2*maxn];

int findpar(int u){
    if(u!=par[u]) return par[u]=findpar(par[u]);
    return u;
}
void unions(int u,int v){
    u=findpar(u);v=findpar(v);
    if(u!=v) par[v]=u;
}

int n,m,q,sum[maxn],nxt[maxn],pre[maxn];
pii S[maxn][maxl];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m >> q;
    for(int i=0;i<n*m;i++) par[i]=i,lt[i]=n,rt[i]=0;
    for(int i=0;i<n;i++) for(int j=0;j<m-1;j++){
        char C;cin >> C;
        if(C=='1') unions(i*m+j,i*m+j+1);
    }
    for(int i=0;i<n-1;i++) for(int j=0;j<m;j++){
        char C;cin >> C;
        if(C=='1') unions(i*m+j,(i+1)*m+j);
    }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        int p=findpar(i*m+j);
        lt[p]=min(lt[p],i);
        rt[p]=max(rt[p],i);
    }
    for(int i=0;i<n*m;i++){
        if(lt[i]>rt[i]) continue;
        nxt[lt[i]]=max(nxt[lt[i]],rt[i]);
        //cout << "range " << lt[i] << ' ' << rt[i] << '\n';
    }
    for(int i=1;i<n;i++) nxt[i]=max({i,nxt[i],nxt[i-1]});
    for(int i=1;i<n;i++){
        if(nxt[i-1]<=i-1) sum[i]++;
        sum[i]+=sum[i-1];
    }
    for(int i=0;i<n;i++){
        int x;cin >> x;
        pre[i]=(i?pre[i-1]:-1);
        if(x==1) pre[i]=i;
    }
    for(int i=0;i<n;i++) S[i][0]={i,max(i,pre[nxt[i]])};
    auto g = [&](int i,int j,int k){
        if(i<0) return i;
        return S[i][j][k];
    };
    auto up = [&](int x){
        if(x==-1) return -1;
        else return max(x,nxt[x]);
    };
    for(int j=1;j<20;j++){
        for(int i=0;i<n;i++){
            S[i][j][0]=max(g(g(i,j-1,0),j-1,1),g(g(i,j-1,1),j-1,0));
            S[i][j][1]=max({g(g(i,j-1,1),j-1,1),g(i,j,0),g(i,j,1),g(up(g(i,j-1,0)),j-1,0)});
        }
    }
    while(q--){
        int sz;cin >> sz;
        vector<int> cc;
        for(int i=0;i<sz;i++){
            int x,y;cin >> x >> y;x--;y--;
            x=findpar(x*m+y);
            cc.push_back(x);
        }
        sort(cc.begin(),cc.end());
        cc.erase(unique(cc.begin(),cc.end()),cc.end());
        if((int)cc.size()==1){
            cout << 0 << '\n';
            continue;
        }
        vector<pii> a;
        int L=n,R=0;
        for(int x:cc){
            L=min(L,rt[x]);
            R=max(R,lt[x]);
            a.push_back({lt[x],rt[x]});
        }
        if(L<R && sum[R]-sum[L]>0){
            cout << -1 << '\n';
            continue;
        }
        sort(a.begin(),a.end(),[&](pii x,pii y){
            return pii{x[0],-x[1]}<pii{y[0],-y[1]};
        });
        {
            vector<pii> st;
            for(pii x:a){
                while(!st.empty() && st.back()[1]>=x[1]) st.pop_back();
                st.push_back(x);
            }
            a=st;
        }
        auto f = [&](int p){
            if(p==-1) return -1;
            int pos=upper_bound(a.begin(),a.end(),pii{p,inf})-a.begin();
            if(pos>0 && p<=a[pos-1][1]) return -1;
            return pos;
        };
        int ans=1;
        pii dp={-1,pre[L]};
        while(dp[1]<R){
            int t0=f(dp[0]),t1=f(dp[1]);
            //cout << '*' << t0 << ' ' << t1 << '\n';
            if(t0>=0 && t1>=0){
                auto get = [&](pii a,int i){
                    int a0=g(a[0],i,1),a1=g(a[1],i,0);
                    int b0=g(up(a[0]),i,0),b1=g(a[1],i,1);
                    return pii{max(a0,a1),max({a0,a1,b0,b1})};
                };
                int mx=R,pos=t1;
                if(pos<(int)a.size()) mx=min(mx,a[pos][0]);
                for(int i=19;i>=0;i--){
                    auto [x,y]=get(dp,i);
                    if(x<mx && y<mx) dp={x,y},ans+=(1<<i);
                }
            }
            if(dp[1]>=R) break;
            auto jmp = [&](int x){
                if(x==-1) return -1;
                int res=nxt[x];
                int pos=upper_bound(a.begin(),a.end(),pii{x,inf})-a.begin();
                if(pos<(int)a.size()) res=min(res,a[pos][1]);
                return res;
            };
            pii ndp{dp[1],-1};
            ndp[1]=max({pre[jmp(dp[1])],jmp(dp[0]),dp[1]});
            ans++;dp=ndp;
            //cout << '*' << dp[0] << ' ' << dp[1] << '\n';
        }
        cout << ans << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 195 ms 118932 KB Output is correct
3 Correct 17 ms 16472 KB Output is correct
4 Correct 23 ms 19032 KB Output is correct
5 Correct 42 ms 19012 KB Output is correct
6 Correct 25 ms 19208 KB Output is correct
7 Correct 157 ms 118872 KB Output is correct
8 Correct 179 ms 118972 KB Output is correct
9 Correct 159 ms 118864 KB Output is correct
10 Correct 19 ms 16560 KB Output is correct
11 Correct 126 ms 85588 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 195 ms 118932 KB Output is correct
3 Correct 17 ms 16472 KB Output is correct
4 Correct 23 ms 19032 KB Output is correct
5 Correct 42 ms 19012 KB Output is correct
6 Correct 25 ms 19208 KB Output is correct
7 Correct 157 ms 118872 KB Output is correct
8 Correct 179 ms 118972 KB Output is correct
9 Correct 159 ms 118864 KB Output is correct
10 Correct 19 ms 16560 KB Output is correct
11 Correct 126 ms 85588 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 219 ms 118868 KB Output is correct
14 Correct 50 ms 44368 KB Output is correct
15 Correct 39 ms 19020 KB Output is correct
16 Correct 27 ms 19028 KB Output is correct
17 Correct 27 ms 19024 KB Output is correct
18 Correct 194 ms 118828 KB Output is correct
19 Correct 149 ms 118868 KB Output is correct
20 Correct 18 ms 16464 KB Output is correct
21 Correct 114 ms 85568 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 195 ms 118932 KB Output is correct
3 Correct 17 ms 16472 KB Output is correct
4 Correct 23 ms 19032 KB Output is correct
5 Correct 42 ms 19012 KB Output is correct
6 Correct 25 ms 19208 KB Output is correct
7 Correct 157 ms 118872 KB Output is correct
8 Correct 179 ms 118972 KB Output is correct
9 Correct 159 ms 118864 KB Output is correct
10 Correct 19 ms 16560 KB Output is correct
11 Correct 126 ms 85588 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 219 ms 118868 KB Output is correct
14 Correct 50 ms 44368 KB Output is correct
15 Correct 39 ms 19020 KB Output is correct
16 Correct 27 ms 19028 KB Output is correct
17 Correct 27 ms 19024 KB Output is correct
18 Correct 194 ms 118828 KB Output is correct
19 Correct 149 ms 118868 KB Output is correct
20 Correct 18 ms 16464 KB Output is correct
21 Correct 114 ms 85568 KB Output is correct
22 Correct 1 ms 8536 KB Output is correct
23 Correct 195 ms 118864 KB Output is correct
24 Correct 172 ms 90192 KB Output is correct
25 Correct 55 ms 18996 KB Output is correct
26 Correct 49 ms 20276 KB Output is correct
27 Correct 68 ms 21104 KB Output is correct
28 Correct 196 ms 121012 KB Output is correct
29 Correct 183 ms 120792 KB Output is correct
30 Correct 178 ms 120884 KB Output is correct
31 Correct 176 ms 118780 KB Output is correct
32 Correct 205 ms 123232 KB Output is correct
33 Correct 58 ms 19040 KB Output is correct
34 Correct 122 ms 85588 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 195 ms 118932 KB Output is correct
3 Correct 17 ms 16472 KB Output is correct
4 Correct 23 ms 19032 KB Output is correct
5 Correct 42 ms 19012 KB Output is correct
6 Correct 25 ms 19208 KB Output is correct
7 Correct 157 ms 118872 KB Output is correct
8 Correct 179 ms 118972 KB Output is correct
9 Correct 159 ms 118864 KB Output is correct
10 Correct 19 ms 16560 KB Output is correct
11 Correct 126 ms 85588 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 219 ms 118868 KB Output is correct
14 Correct 50 ms 44368 KB Output is correct
15 Correct 39 ms 19020 KB Output is correct
16 Correct 27 ms 19028 KB Output is correct
17 Correct 27 ms 19024 KB Output is correct
18 Correct 194 ms 118828 KB Output is correct
19 Correct 149 ms 118868 KB Output is correct
20 Correct 18 ms 16464 KB Output is correct
21 Correct 114 ms 85568 KB Output is correct
22 Correct 444 ms 121044 KB Output is correct
23 Correct 261 ms 120604 KB Output is correct
24 Correct 102 ms 44372 KB Output is correct
25 Correct 96 ms 18512 KB Output is correct
26 Correct 105 ms 20688 KB Output is correct
27 Correct 88 ms 20820 KB Output is correct
28 Correct 56 ms 20644 KB Output is correct
29 Correct 212 ms 120360 KB Output is correct
30 Correct 230 ms 120440 KB Output is correct
31 Correct 231 ms 120400 KB Output is correct
32 Correct 210 ms 120400 KB Output is correct
33 Correct 71 ms 18316 KB Output is correct
34 Correct 247 ms 87220 KB Output is correct
35 Correct 202 ms 70224 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 195 ms 118932 KB Output is correct
3 Correct 17 ms 16472 KB Output is correct
4 Correct 23 ms 19032 KB Output is correct
5 Correct 42 ms 19012 KB Output is correct
6 Correct 25 ms 19208 KB Output is correct
7 Correct 157 ms 118872 KB Output is correct
8 Correct 179 ms 118972 KB Output is correct
9 Correct 159 ms 118864 KB Output is correct
10 Correct 19 ms 16560 KB Output is correct
11 Correct 126 ms 85588 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 219 ms 118868 KB Output is correct
14 Correct 50 ms 44368 KB Output is correct
15 Correct 39 ms 19020 KB Output is correct
16 Correct 27 ms 19028 KB Output is correct
17 Correct 27 ms 19024 KB Output is correct
18 Correct 194 ms 118828 KB Output is correct
19 Correct 149 ms 118868 KB Output is correct
20 Correct 18 ms 16464 KB Output is correct
21 Correct 114 ms 85568 KB Output is correct
22 Correct 1 ms 8536 KB Output is correct
23 Correct 195 ms 118864 KB Output is correct
24 Correct 172 ms 90192 KB Output is correct
25 Correct 55 ms 18996 KB Output is correct
26 Correct 49 ms 20276 KB Output is correct
27 Correct 68 ms 21104 KB Output is correct
28 Correct 196 ms 121012 KB Output is correct
29 Correct 183 ms 120792 KB Output is correct
30 Correct 178 ms 120884 KB Output is correct
31 Correct 176 ms 118780 KB Output is correct
32 Correct 205 ms 123232 KB Output is correct
33 Correct 58 ms 19040 KB Output is correct
34 Correct 122 ms 85588 KB Output is correct
35 Correct 444 ms 121044 KB Output is correct
36 Correct 261 ms 120604 KB Output is correct
37 Correct 102 ms 44372 KB Output is correct
38 Correct 96 ms 18512 KB Output is correct
39 Correct 105 ms 20688 KB Output is correct
40 Correct 88 ms 20820 KB Output is correct
41 Correct 56 ms 20644 KB Output is correct
42 Correct 212 ms 120360 KB Output is correct
43 Correct 230 ms 120440 KB Output is correct
44 Correct 231 ms 120400 KB Output is correct
45 Correct 210 ms 120400 KB Output is correct
46 Correct 71 ms 18316 KB Output is correct
47 Correct 247 ms 87220 KB Output is correct
48 Correct 202 ms 70224 KB Output is correct
49 Correct 476 ms 120420 KB Output is correct
50 Correct 385 ms 120148 KB Output is correct
51 Correct 109 ms 43860 KB Output is correct
52 Correct 73 ms 23376 KB Output is correct
53 Correct 70 ms 21660 KB Output is correct
54 Correct 84 ms 21484 KB Output is correct
55 Correct 218 ms 123064 KB Output is correct
56 Correct 201 ms 121104 KB Output is correct
57 Correct 206 ms 122196 KB Output is correct
58 Correct 214 ms 120400 KB Output is correct
59 Correct 64 ms 18700 KB Output is correct
60 Correct 332 ms 87232 KB Output is correct
61 Correct 274 ms 70388 KB Output is correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 195 ms 118932 KB Output is correct
3 Correct 17 ms 16472 KB Output is correct
4 Correct 23 ms 19032 KB Output is correct
5 Correct 42 ms 19012 KB Output is correct
6 Correct 25 ms 19208 KB Output is correct
7 Correct 157 ms 118872 KB Output is correct
8 Correct 179 ms 118972 KB Output is correct
9 Correct 159 ms 118864 KB Output is correct
10 Correct 19 ms 16560 KB Output is correct
11 Correct 126 ms 85588 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 219 ms 118868 KB Output is correct
14 Correct 50 ms 44368 KB Output is correct
15 Correct 39 ms 19020 KB Output is correct
16 Correct 27 ms 19028 KB Output is correct
17 Correct 27 ms 19024 KB Output is correct
18 Correct 194 ms 118828 KB Output is correct
19 Correct 149 ms 118868 KB Output is correct
20 Correct 18 ms 16464 KB Output is correct
21 Correct 114 ms 85568 KB Output is correct
22 Correct 1 ms 8536 KB Output is correct
23 Correct 195 ms 118864 KB Output is correct
24 Correct 172 ms 90192 KB Output is correct
25 Correct 55 ms 18996 KB Output is correct
26 Correct 49 ms 20276 KB Output is correct
27 Correct 68 ms 21104 KB Output is correct
28 Correct 196 ms 121012 KB Output is correct
29 Correct 183 ms 120792 KB Output is correct
30 Correct 178 ms 120884 KB Output is correct
31 Correct 176 ms 118780 KB Output is correct
32 Correct 205 ms 123232 KB Output is correct
33 Correct 58 ms 19040 KB Output is correct
34 Correct 122 ms 85588 KB Output is correct
35 Incorrect 1 ms 8536 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 195 ms 118932 KB Output is correct
3 Correct 17 ms 16472 KB Output is correct
4 Correct 23 ms 19032 KB Output is correct
5 Correct 42 ms 19012 KB Output is correct
6 Correct 25 ms 19208 KB Output is correct
7 Correct 157 ms 118872 KB Output is correct
8 Correct 179 ms 118972 KB Output is correct
9 Correct 159 ms 118864 KB Output is correct
10 Correct 19 ms 16560 KB Output is correct
11 Correct 126 ms 85588 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 219 ms 118868 KB Output is correct
14 Correct 50 ms 44368 KB Output is correct
15 Correct 39 ms 19020 KB Output is correct
16 Correct 27 ms 19028 KB Output is correct
17 Correct 27 ms 19024 KB Output is correct
18 Correct 194 ms 118828 KB Output is correct
19 Correct 149 ms 118868 KB Output is correct
20 Correct 18 ms 16464 KB Output is correct
21 Correct 114 ms 85568 KB Output is correct
22 Correct 444 ms 121044 KB Output is correct
23 Correct 261 ms 120604 KB Output is correct
24 Correct 102 ms 44372 KB Output is correct
25 Correct 96 ms 18512 KB Output is correct
26 Correct 105 ms 20688 KB Output is correct
27 Correct 88 ms 20820 KB Output is correct
28 Correct 56 ms 20644 KB Output is correct
29 Correct 212 ms 120360 KB Output is correct
30 Correct 230 ms 120440 KB Output is correct
31 Correct 231 ms 120400 KB Output is correct
32 Correct 210 ms 120400 KB Output is correct
33 Correct 71 ms 18316 KB Output is correct
34 Correct 247 ms 87220 KB Output is correct
35 Correct 202 ms 70224 KB Output is correct
36 Incorrect 1 ms 8540 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 195 ms 118932 KB Output is correct
3 Correct 17 ms 16472 KB Output is correct
4 Correct 23 ms 19032 KB Output is correct
5 Correct 42 ms 19012 KB Output is correct
6 Correct 25 ms 19208 KB Output is correct
7 Correct 157 ms 118872 KB Output is correct
8 Correct 179 ms 118972 KB Output is correct
9 Correct 159 ms 118864 KB Output is correct
10 Correct 19 ms 16560 KB Output is correct
11 Correct 126 ms 85588 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 219 ms 118868 KB Output is correct
14 Correct 50 ms 44368 KB Output is correct
15 Correct 39 ms 19020 KB Output is correct
16 Correct 27 ms 19028 KB Output is correct
17 Correct 27 ms 19024 KB Output is correct
18 Correct 194 ms 118828 KB Output is correct
19 Correct 149 ms 118868 KB Output is correct
20 Correct 18 ms 16464 KB Output is correct
21 Correct 114 ms 85568 KB Output is correct
22 Correct 1 ms 8536 KB Output is correct
23 Correct 195 ms 118864 KB Output is correct
24 Correct 172 ms 90192 KB Output is correct
25 Correct 55 ms 18996 KB Output is correct
26 Correct 49 ms 20276 KB Output is correct
27 Correct 68 ms 21104 KB Output is correct
28 Correct 196 ms 121012 KB Output is correct
29 Correct 183 ms 120792 KB Output is correct
30 Correct 178 ms 120884 KB Output is correct
31 Correct 176 ms 118780 KB Output is correct
32 Correct 205 ms 123232 KB Output is correct
33 Correct 58 ms 19040 KB Output is correct
34 Correct 122 ms 85588 KB Output is correct
35 Correct 444 ms 121044 KB Output is correct
36 Correct 261 ms 120604 KB Output is correct
37 Correct 102 ms 44372 KB Output is correct
38 Correct 96 ms 18512 KB Output is correct
39 Correct 105 ms 20688 KB Output is correct
40 Correct 88 ms 20820 KB Output is correct
41 Correct 56 ms 20644 KB Output is correct
42 Correct 212 ms 120360 KB Output is correct
43 Correct 230 ms 120440 KB Output is correct
44 Correct 231 ms 120400 KB Output is correct
45 Correct 210 ms 120400 KB Output is correct
46 Correct 71 ms 18316 KB Output is correct
47 Correct 247 ms 87220 KB Output is correct
48 Correct 202 ms 70224 KB Output is correct
49 Correct 476 ms 120420 KB Output is correct
50 Correct 385 ms 120148 KB Output is correct
51 Correct 109 ms 43860 KB Output is correct
52 Correct 73 ms 23376 KB Output is correct
53 Correct 70 ms 21660 KB Output is correct
54 Correct 84 ms 21484 KB Output is correct
55 Correct 218 ms 123064 KB Output is correct
56 Correct 201 ms 121104 KB Output is correct
57 Correct 206 ms 122196 KB Output is correct
58 Correct 214 ms 120400 KB Output is correct
59 Correct 64 ms 18700 KB Output is correct
60 Correct 332 ms 87232 KB Output is correct
61 Correct 274 ms 70388 KB Output is correct
62 Incorrect 1 ms 8536 KB Output isn't correct
63 Halted 0 ms 0 KB -