oj.uz

Submission #1020212

# Submission time Handle Problem Language Result Execution time Memory
1020212 2024-07-11T17:13:03 Z bachhoangxuan Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 176 ms 73348 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;add_edge(f[i],rev(id));
            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;add_edge(f[i],rev(id));
            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 20 ms 38236 KB Output is correct
2 Correct 20 ms 37980 KB Output is correct
3 Correct 19 ms 38236 KB Output is correct
4 Correct 19 ms 38236 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 38236 KB Output is correct
2 Correct 20 ms 38236 KB Output is correct
3 Correct 19 ms 38236 KB Output is correct
4 Correct 19 ms 38140 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38236 KB Output is correct
2 Correct 17 ms 38164 KB Output is correct
3 Correct 20 ms 38236 KB Output is correct
4 Correct 25 ms 38240 KB Output is correct
5 Correct 19 ms 38236 KB Output is correct
6 Correct 18 ms 38236 KB Output is correct
7 Correct 19 ms 38236 KB Output is correct
8 Correct 20 ms 38232 KB Output is correct
9 Correct 20 ms 38236 KB Output is correct
10 Correct 19 ms 38232 KB Output is correct
11 Correct 20 ms 38236 KB Output is correct
12 Correct 19 ms 38136 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 38236 KB Output is correct
2 Correct 19 ms 38236 KB Output is correct
3 Correct 18 ms 38060 KB Output is correct
4 Correct 19 ms 38288 KB Output is correct
5 Correct 19 ms 38236 KB Output is correct
6 Correct 18 ms 38236 KB Output is correct
7 Correct 20 ms 38268 KB Output is correct
8 Correct 21 ms 38356 KB Output is correct
9 Correct 19 ms 38380 KB Output is correct
10 Correct 20 ms 38420 KB Output is correct
11 Correct 20 ms 38412 KB Output is correct
12 Correct 18 ms 38236 KB Output is correct
13 Correct 19 ms 38320 KB Output is correct
14 Incorrect 22 ms 38556 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 20 ms 38236 KB Output is correct
2 Correct 20 ms 37980 KB Output is correct
3 Correct 19 ms 38236 KB Output is correct
4 Correct 19 ms 38236 KB Output is correct
5 Correct 82 ms 54724 KB Output is correct
6 Correct 91 ms 54680 KB Output is correct
7 Correct 84 ms 54720 KB Output is correct
8 Correct 85 ms 54716 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 38236 KB Output is correct
2 Correct 20 ms 38236 KB Output is correct
3 Correct 19 ms 38236 KB Output is correct
4 Correct 19 ms 38140 KB Output is correct
5 Correct 106 ms 62408 KB Output is correct
6 Correct 94 ms 58272 KB Output is correct
7 Correct 96 ms 60348 KB Output is correct
8 Correct 96 ms 61032 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38236 KB Output is correct
2 Correct 17 ms 38164 KB Output is correct
3 Correct 20 ms 38236 KB Output is correct
4 Correct 25 ms 38240 KB Output is correct
5 Correct 19 ms 38236 KB Output is correct
6 Correct 18 ms 38236 KB Output is correct
7 Correct 19 ms 38236 KB Output is correct
8 Correct 20 ms 38232 KB Output is correct
9 Correct 20 ms 38236 KB Output is correct
10 Correct 19 ms 38232 KB Output is correct
11 Correct 20 ms 38236 KB Output is correct
12 Correct 19 ms 38136 KB Output is correct
13 Correct 94 ms 59608 KB Output is correct
14 Correct 90 ms 59012 KB Output is correct
15 Correct 103 ms 60292 KB Output is correct
16 Correct 104 ms 58064 KB Output is correct
17 Correct 97 ms 59840 KB Output is correct
18 Correct 88 ms 57276 KB Output is correct
19 Correct 129 ms 70804 KB Output is correct
20 Correct 160 ms 72024 KB Output is correct
21 Correct 144 ms 73288 KB Output is correct
22 Correct 95 ms 62656 KB Output is correct
23 Correct 176 ms 73348 KB Output is correct
24 Correct 93 ms 62280 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 38236 KB Output is correct
2 Correct 19 ms 38236 KB Output is correct
3 Correct 18 ms 38060 KB Output is correct
4 Correct 19 ms 38288 KB Output is correct
5 Correct 19 ms 38236 KB Output is correct
6 Correct 18 ms 38236 KB Output is correct
7 Correct 20 ms 38268 KB Output is correct
8 Correct 21 ms 38356 KB Output is correct
9 Correct 19 ms 38380 KB Output is correct
10 Correct 20 ms 38420 KB Output is correct
11 Correct 20 ms 38412 KB Output is correct
12 Correct 18 ms 38236 KB Output is correct
13 Correct 19 ms 38320 KB Output is correct
14 Incorrect 22 ms 38556 KB Output isn't correct
15 Halted 0 ms 0 KB -