Submission #223528

#	Time	Username	Problem	Language	Result	Execution time	Memory
223528		Minnakhmetov	Hamburg Steak (JOI20_hamburg)	C++14	3 / 100	1302 ms	38700 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int INF = 1e9 + 5, N = 2e5 + 5, M = 2005;

struct R {
	int xl = -1, yl = -1, xr = INF, yr = INF;

	bool is_empty() {
		return xl > xr || yl > yr;
	}
} rect[N];

int w[M][M], col[N];
int n, k;

R get_intersection(R a, R b) {
	return {max(a.xl, b.xl), max(a.yl, b.yl), min(a.xr, b.xr), min(a.yr, b.yr)};
}

void dfs(int node, int c) {
	col[node] = c;
	for (int i = 0; i < n; i++) {
		if (w[node][i] && !col[i]) {
			dfs(i, 3 - c);
		}
	}
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
    	cin >> rect[i].xl >> rect[i].yl >> rect[i].xr >> rect[i].yr;
    }

    if (k == 1) {
    	R inter;
    	for (int i = 0; i < n; i++) {
    		inter = get_intersection(inter, rect[i]);
    	}
    	cout << inter.xl << " " << inter.yl << "\n";
    }
    else if (k == 2) {
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			w[i][j] = get_intersection(rect[i], rect[j]).is_empty();
    		}
    	}
    	for (int i = 0; i < n; i++) {
    		if (!col[i]) {
    			dfs(i, 1);
    		}
    	}
    	R inter[2];
    	for (int i = 0; i < n; i++) {
    		inter[col[i] - 1] = get_intersection(inter[col[i] - 1], rect[i]);
    	}

    	for (int i = 0; i < 2; i++) {
    		cout << inter[i].xl << " " << inter[i].yl << "\n";
    	}
    }

    return 0;
}

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