oj.uz

Submission #1020210

# Submission time Handle Problem Language Result Execution time Memory
1020210 2024-07-11T17:11:31 Z bachhoangxuan Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 177 ms 73948 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int inf = 1e9;
#define pii pair<int,int>
#define piii pair<pii,int>
#define fi first
#define se second

struct rec{
    int l,r,u,d;
    rec(int l=0,int r=0,int u=0,int d=0):l(l),r(r),u(u),d(d){}
};

int N,K;
vector<rec> A;
int rev(int x){
    return (x>2*N?x-2*N:x+2*N);
}

int T,f[maxn],lt[4],rt[4];
vector<int> edge[8*maxn];
vector<piii> cc[4];

void add_edge(int u,int v){
    edge[u].push_back(v);
}

int num[8*maxn],low[8*maxn],scc[8*maxn],cnt;
bool inst[8*maxn];
vector<int> st;

void dfs(int u){
    num[u]=low[u]=++T;
    inst[u]=true;st.push_back(u);
    for(int v:edge[u]){
        if(!num[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(inst[v]) low[u]=min(low[u],num[v]);
    }
    if(low[u]==num[u]){
        int v=-1;cnt++;
        do{
            v=st.back();
            scc[v]=cnt;
            st.pop_back();
        }while(v!=u);
    }
}

void solve(){
    int L=0,R=inf,U=inf,D=0;
    for(auto [l,r,u,d]:A) L=max(L,l),R=min(R,r),U=min(U,u),D=max(D,d);
    for(int i=0;i<4;i++) lt[i]=0,rt[i]=inf;

    auto add = [&](int l,int r,int u,int d){
        int k=0,op=-1,oq=-1;
        pii p,q;
        if(l<=L && L<=r) q={d,u},oq=0,swap(p,q),swap(op,oq),k++;
        if(l<=R && R<=r) q={d,u},oq=1,swap(p,q),swap(op,oq),k++;
        if(d<=D && D<=u) q={l,r},oq=2,swap(p,q),swap(op,oq),k++;
        if(d<=U && U<=u) q={l,r},oq=3,swap(p,q),swap(op,oq),k++;
        if(k>=3) return;
        if(k==1){
            lt[op]=max(lt[op],p.fi);
            rt[op]=min(rt[op],p.se);
        }
        else{
            cc[op].push_back({p,++T});
            cc[oq].push_back({q,++T});
            add_edge(rev(T-1),T);
            add_edge(rev(T),T-1);
        }
    };
    for(auto [l,r,u,d]:A) add(l,r,u,d);

    int S=T;T+=2*N;
    for(int t=0;t<4;t++){
        sort(cc[t].begin(),cc[t].end(),[&](piii a,piii b){
            return a.fi.se<b.fi.se;
        });
        int sz=(int)cc[t].size();
        for(int i=0;i<sz;i++){
            auto [p,id]=cc[t][i];
            if(p.se<lt[t] || rt[t]<p.fi) add_edge(id,rev(id));
            f[i]=++T;
            if(i) add_edge(f[i],f[i-1]);
            int l=-1,r=i-1;
            while(l<r){
                int m=(l+r+1)>>1;
                if(cc[t][m].fi.se<p.fi) l=m;
                else r=m-1;
            }
            if(l>=0) add_edge(id,f[l]);
        }
        sort(cc[t].begin(),cc[t].end(),[&](piii a,piii b){
            return a.fi.fi<b.fi.fi;
        });
        for(int i=sz-1;i>=0;i--){
            auto [p,id]=cc[t][i];
            f[i]=++T;
            if(i<sz-1) add_edge(f[i],f[i+1]);
            int l=i+1,r=sz;
            while(l<r){
                int m=(l+r)>>1;
                if(cc[t][m].fi.fi>p.se) r=m;
                else l=m+1;
            }
            if(l<sz) add_edge(id,f[l]);
        }
    }
    int M=T;T=0;
    for(int i=1;i<=M;i++) if(!num[i]) dfs(i);

    vector<bool> use(S+1);
    for(int i=1;i<=S;i++) use[i]=(scc[i]<scc[rev(i)]);
    for(int t=0;t<4;t++){
        for(auto [p,id]:cc[t]){
            if(use[id]) lt[t]=max(lt[t],p.fi),rt[t]=min(rt[t],p.se);
        }
    }
    cout << L << ' ' << lt[0] << '\n';
    cout << R << ' ' << lt[1] << '\n';
    cout << lt[2] << ' ' << D << '\n';
    cout << lt[3] << ' ' << U << '\n';
}

bool check=false;
vector<pii> cur;

vector<rec> get(int x,int y,vector<rec> a){
    cur.push_back({x,y});
    vector<rec> res;
    for(auto [l,r,u,d]:a) if(x<l || r<x || y<d || u<y) res.push_back(rec(l,r,u,d));
    return res;
}

void dfs(int k,vector<rec> a){
    if(check) return;
    if(!k){
        if(!a.empty() || check) return;
        check=true;
        for(auto [x,y]:cur) cout << x << ' ' << y << '\n';
        return;
    }
    int L=0,R=inf,U=inf,D=0;
    for(auto [l,r,u,d]:a) L=max(L,l),R=min(R,r),U=min(U,u),D=max(D,d);
    dfs(k-1,get(L,U,a));cur.pop_back();
    dfs(k-1,get(L,D,a));cur.pop_back();
    dfs(k-1,get(R,U,a));cur.pop_back();
    dfs(k-1,get(R,D,a));cur.pop_back();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> K;
    for(int i=0;i<N;i++){
        int l,r,u,d;cin >> l >> d >> r >> u;
        A.push_back(rec(l,r,u,d));
    }
    dfs(K,A);
    if(check) return 0;
    solve();
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38080 KB Output is correct
2 Correct 20 ms 38036 KB Output is correct
3 Correct 19 ms 38248 KB Output is correct
4 Correct 18 ms 38232 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 38068 KB Output is correct
2 Correct 18 ms 38236 KB Output is correct
3 Correct 23 ms 38308 KB Output is correct
4 Correct 23 ms 38236 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 38236 KB Output is correct
2 Correct 22 ms 38140 KB Output is correct
3 Correct 19 ms 38312 KB Output is correct
4 Correct 20 ms 38232 KB Output is correct
5 Correct 18 ms 38236 KB Output is correct
6 Correct 24 ms 38236 KB Output is correct
7 Correct 20 ms 38248 KB Output is correct
8 Correct 19 ms 38296 KB Output is correct
9 Correct 17 ms 38412 KB Output is correct
10 Correct 17 ms 38140 KB Output is correct
11 Correct 21 ms 38236 KB Output is correct
12 Correct 20 ms 38036 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38048 KB Output is correct
2 Correct 18 ms 38052 KB Output is correct
3 Correct 20 ms 38092 KB Output is correct
4 Correct 18 ms 38052 KB Output is correct
5 Correct 19 ms 38204 KB Output is correct
6 Correct 20 ms 38228 KB Output is correct
7 Correct 23 ms 38312 KB Output is correct
8 Correct 26 ms 38432 KB Output is correct
9 Correct 20 ms 38280 KB Output is correct
10 Correct 23 ms 38300 KB Output is correct
11 Correct 22 ms 38412 KB Output is correct
12 Correct 19 ms 38284 KB Output is correct
13 Correct 18 ms 38236 KB Output is correct
14 Incorrect 23 ms 38604 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38080 KB Output is correct
2 Correct 20 ms 38036 KB Output is correct
3 Correct 19 ms 38248 KB Output is correct
4 Correct 18 ms 38232 KB Output is correct
5 Correct 88 ms 55100 KB Output is correct
6 Correct 88 ms 55088 KB Output is correct
7 Correct 83 ms 55100 KB Output is correct
8 Correct 86 ms 55120 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 38068 KB Output is correct
2 Correct 18 ms 38236 KB Output is correct
3 Correct 23 ms 38308 KB Output is correct
4 Correct 23 ms 38236 KB Output is correct
5 Correct 110 ms 62704 KB Output is correct
6 Correct 92 ms 58872 KB Output is correct
7 Correct 97 ms 61012 KB Output is correct
8 Correct 95 ms 61724 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 38236 KB Output is correct
2 Correct 22 ms 38140 KB Output is correct
3 Correct 19 ms 38312 KB Output is correct
4 Correct 20 ms 38232 KB Output is correct
5 Correct 18 ms 38236 KB Output is correct
6 Correct 24 ms 38236 KB Output is correct
7 Correct 20 ms 38248 KB Output is correct
8 Correct 19 ms 38296 KB Output is correct
9 Correct 17 ms 38412 KB Output is correct
10 Correct 17 ms 38140 KB Output is correct
11 Correct 21 ms 38236 KB Output is correct
12 Correct 20 ms 38036 KB Output is correct
13 Correct 98 ms 60348 KB Output is correct
14 Correct 95 ms 59588 KB Output is correct
15 Correct 111 ms 60824 KB Output is correct
16 Correct 91 ms 58580 KB Output is correct
17 Correct 92 ms 60352 KB Output is correct
18 Correct 99 ms 57920 KB Output is correct
19 Correct 131 ms 71544 KB Output is correct
20 Correct 149 ms 72540 KB Output is correct
21 Correct 150 ms 73948 KB Output is correct
22 Correct 97 ms 62824 KB Output is correct
23 Correct 177 ms 73888 KB Output is correct
24 Correct 96 ms 62796 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38048 KB Output is correct
2 Correct 18 ms 38052 KB Output is correct
3 Correct 20 ms 38092 KB Output is correct
4 Correct 18 ms 38052 KB Output is correct
5 Correct 19 ms 38204 KB Output is correct
6 Correct 20 ms 38228 KB Output is correct
7 Correct 23 ms 38312 KB Output is correct
8 Correct 26 ms 38432 KB Output is correct
9 Correct 20 ms 38280 KB Output is correct
10 Correct 23 ms 38300 KB Output is correct
11 Correct 22 ms 38412 KB Output is correct
12 Correct 19 ms 38284 KB Output is correct
13 Correct 18 ms 38236 KB Output is correct
14 Incorrect 23 ms 38604 KB Output isn't correct
15 Halted 0 ms 0 KB -