oj.uz

Submission #223528

# Submission time Handle Problem Language Result Execution time Memory
223528 2020-04-15T10:54:01 Z Minnakhmetov Hamburg Steak (JOI20_hamburg) C++14
3 / 100
 1302 ms 38700 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15520 KB Output is correct
2 Correct 35 ms 16128 KB Output is correct
3 Correct 45 ms 16000 KB Output is correct
4 Correct 62 ms 15608 KB Output is correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 120 ms 3448 KB Output is correct
6 Correct 119 ms 3448 KB Output is correct
7 Correct 95 ms 3704 KB Output is correct
8 Correct 103 ms 3448 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15520 KB Output is correct
2 Correct 35 ms 16128 KB Output is correct
3 Correct 45 ms 16000 KB Output is correct
4 Correct 62 ms 15608 KB Output is correct
5 Runtime error 1302 ms 38700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -