Submission #942966

#	Time	Username	Problem	Language	Result	Execution time	Memory
942966		guagua0407	Hamburg Steak (JOI20_hamburg)	C++17	0 / 100	55 ms	27732 KiB

hamburg

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int inf=1e9+5;
const int mxn=2e5+5;
vector<int> adj[mxn];
int x1[mxn];
int x2[mxn];
int Y1[mxn];
int Y2[mxn];
bool visited[mxn];
int depth[mxn];
int c[mxn];
bool up[mxn];

void dfs(int v,int p=-1){
    if(p!=-1) depth[v]=depth[p]+1;
    visited[v]=true;
    for(auto u:adj[v]){
        if(visited[u]){
            if(u!=p and depth[u]<depth[v]){
                if(up[u]){

                }
                up[v]=true;
            }
            continue;
        }
        c[u]=c[v]^1;
        dfs(u,v);
    }
}

bool cross(int a,int b){
    bool ok=true;
    if(x1[a]>x1[b]) swap(a,b);
    ok&=(x2[a]>=x1[b]);
    if(Y1[a]>Y1[b]) swap(a,b);
    ok&=(Y2[a]>=Y1[b]);
    return ok;
}

pair<int,int> cal(vector<int> vec){
    if(vec.empty()){
        return {0,0};
    }
    int mnx=inf;
    int mny=inf;
    for(auto v:vec){
        mnx=min(mnx,x2[v]);
        mny=min(mny,Y2[v]);
    }
    return {mnx,mny};
}

int main() {_
    int n,k;
    cin>>n>>k;
    int mnx=inf;
    int mny=inf;
    for(int i=0;i<n;i++){
        cin>>x1[i]>>Y1[i]>>x2[i]>>Y2[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) continue;
            if(!cross(i,j)) adj[i].push_back(j);
        }
    }
    for(int i=0;i<n;i++){
        vector<bool> use(3);
        for(auto v:adj[i]){
            if(v>i) continue;
            use[c[v]]=true;
        }
        c[i]=-1;
        for(int j=0;j<3;j++){
            if(!use[j]){
                c[i]=j;
                break;
            }
        }
        assert(c[i]!=-1);
    }
    //return 0;
    vector<int> a,b,C;
    for(int i=0;i<n;i++){
        if(c[i]==0) a.push_back(i);
        else if(c[i]==1) b.push_back(i);
        else C.push_back(i);
    }
    pair<int,int> res=cal(a);
    cout<<res.f<<' '<<res.s<<'\n';
    pair<int,int> res2=cal(b);
    cout<<res2.f<<' '<<res2.s<<'\n';
    pair<int,int> res3=cal(C);
    cout<<res3.f<<' '<<res3.s<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:74:9: warning: unused variable 'mnx' [-Wunused-variable]
   74 |     int mnx=inf;
      |         ^~~
hamburg.cpp:75:9: warning: unused variable 'mny' [-Wunused-variable]
   75 |     int mny=inf;
      |         ^~~
hamburg.cpp: In function 'void setIO(std::string)':
hamburg.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 0 / 1
• Subtask 6: 0 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79