oj.uz

Submission #814005

# Submission time Handle Problem Language Result Execution time Memory
814005 2023-08-08T04:57:35 Z becaido Fountain Parks (IOI21_parks) C++17
5 / 100
 438 ms 85476 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "parks.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#ifdef WAIMAI
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
#endif

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
const int SIZE = 2e5 + 5;

vector<int> adj[SIZE];
map<pair<int, int>, int> mp;
int deg[SIZE], pa[SIZE];
queue<int> q;

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    FOR (i, 0, n - 1) mp[{x[i], y[i]}] = i;
    FOR (i, 0, n - 1) FOR (j, 0, 3) {
        int tx = x[i] + 2 * dx[j];
        int ty = y[i] + 2 * dy[j];
        if (mp.count({tx, ty})) adj[i].pb(mp[{tx, ty}]);
    }
    q.push(0);
    fill(pa, pa + n, -1);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (int np : adj[pos]) if (np != 0 && pa[np] == -1) {
            pa[np] = pos;
            deg[pos]++;
            q.push(np);
        }
    }
    FOR (i, 1, n - 1) if (pa[i] == -1) return 0;
    FOR (i, 0, n - 1) if (!deg[i]) q.push(i);
    vector<int> u, v, a, b;
    set<pair<int, int>> s;
    while (q.size()) {
        int pos = q.front();
        q.pop();
        if (pos == 0) break;
        int lx, ly, rx, ry;
        tie(lx, ly) = make_pair(x[pos], y[pos]);
        tie(rx, ry) = make_pair(x[pa[pos]], y[pa[pos]]);
        u.pb(pos), v.pb(pa[pos]);
        int mx = (lx + rx) / 2, my = (ly + ry) / 2;
        vector<int> id(2);
        if (lx == rx) id[0] = 0, id[1] = 3;
        else id[0] = 1, id[1] = 2;
        for (int i : id) {
            int tx = mx + dx[i], ty = my + dy[i];
            if (s.count({tx, ty})) continue;
            a.pb(tx), b.pb(ty);
            s.emplace(tx, ty);
            break;
        }
        if (u.size() > a.size()) assert(0);
        if (--deg[pa[pos]] == 0) q.push(pa[pos]);
    }
    build(u, v, a, b);
    return 1;
}

/*
in1
5
4 4
4 6
6 4
4 2
2 4
out1
1
4
0 2 5 5
0 1 3 5
3 0 5 3
4 0 3 3

in2
2
2 2
4 6
out2
0
*/

#ifdef WAIMAI
static void check(bool cond, string message) {
	if (!cond) {
		printf("%s\n", message.c_str());
		fclose(stdout);
		exit(0);
	}
}

static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
	check(!build_called, "build is called more than once");
	build_called = true;
	m = u.size();
	check(int(v.size()) == m, "u.size() != v.size()");
	check(int(a.size()) == m, "u.size() != a.size()");
	check(int(b.size()) == m, "u.size() != b.size()");
	_u = u;
	_v = v;
	_a = a;
	_b = b;
}

int main() {
	assert(scanf("%d", &n) == 1);
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	build_called = false;
	const int possible = construct_roads(x, y);

	check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
	if (possible == 1) {
		check(build_called, "construct_roads() returned 1 without calling build()");
	} else {
		check(!build_called, "construct_roads() called build() but returned 0");
	}

	printf("%d\n", possible);
	if (possible == 1) {
		printf("%d\n", m);
		for (int j = 0; j < m; j++) {
			printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
		}
	}
	fclose(stdout);
	return 0;
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 5004 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 172 ms 26980 KB Output is correct
10 Correct 14 ms 7424 KB Output is correct
11 Correct 71 ms 16768 KB Output is correct
12 Correct 22 ms 8500 KB Output is correct
13 Correct 37 ms 10384 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5180 KB Output is correct
16 Correct 167 ms 26908 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 5004 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 172 ms 26980 KB Output is correct
10 Correct 14 ms 7424 KB Output is correct
11 Correct 71 ms 16768 KB Output is correct
12 Correct 22 ms 8500 KB Output is correct
13 Correct 37 ms 10384 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5180 KB Output is correct
16 Correct 167 ms 26908 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4928 KB Output is correct
21 Correct 3 ms 5004 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Runtime error 435 ms 84692 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 5004 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 172 ms 26980 KB Output is correct
10 Correct 14 ms 7424 KB Output is correct
11 Correct 71 ms 16768 KB Output is correct
12 Correct 22 ms 8500 KB Output is correct
13 Correct 37 ms 10384 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5180 KB Output is correct
16 Correct 167 ms 26908 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4928 KB Output is correct
21 Correct 3 ms 5004 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Runtime error 435 ms 84692 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 5004 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 172 ms 26980 KB Output is correct
10 Correct 14 ms 7424 KB Output is correct
11 Correct 71 ms 16768 KB Output is correct
12 Correct 22 ms 8500 KB Output is correct
13 Correct 37 ms 10384 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5180 KB Output is correct
16 Correct 167 ms 26908 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5008 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Runtime error 428 ms 85476 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 5004 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 172 ms 26980 KB Output is correct
10 Correct 14 ms 7424 KB Output is correct
11 Correct 71 ms 16768 KB Output is correct
12 Correct 22 ms 8500 KB Output is correct
13 Correct 37 ms 10384 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5180 KB Output is correct
16 Correct 167 ms 26908 KB Output is correct
17 Correct 438 ms 49324 KB Output is correct
18 Runtime error 419 ms 82672 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5000 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 5004 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 172 ms 26980 KB Output is correct
10 Correct 14 ms 7424 KB Output is correct
11 Correct 71 ms 16768 KB Output is correct
12 Correct 22 ms 8500 KB Output is correct
13 Correct 37 ms 10384 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5180 KB Output is correct
16 Correct 167 ms 26908 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4928 KB Output is correct
21 Correct 3 ms 5004 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Runtime error 435 ms 84692 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -