Submission #942924

#	Time	Username	Problem	Language	Result	Execution time	Memory
942924		guagua0407	Hamburg Steak (JOI20_hamburg)	C++17	1 / 100	3056 ms	276376 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];

void dfs(int v,int p=-1){
    visited[v]=true;
    for(auto u:adj[v]){
        if(visited[u]){
            if(u!=p){
                assert(c[v]!=c[u]);
            }
            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){
    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++){
        if(!visited[i]) dfs(i);
    }
    vector<int> a,b;
    for(int i=0;i<n;i++){
        if(c[i]==0) a.push_back(i);
        else b.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';
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:66:9: warning: unused variable 'mnx' [-Wunused-variable]
   66 |     int mnx=inf;
      |         ^~~
hamburg.cpp:67:9: warning: unused variable 'mny' [-Wunused-variable]
   67 |     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: 1 / 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