oj.uz

Submission #814391

# Submission time Handle Problem Language Result Execution time Memory
814391 2023-08-08T07:13:32 Z becaido Fountain Parks (IOI21_parks) C++17
5 / 100
 429 ms 37952 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;
        if (lx == rx) {
            int y = min(ly, ry);
            if ((lx + y) % 4) a.pb(lx - 1), b.pb(my);
            else a.pb(lx + 1), b.pb(my);
        } else {
            int x = min(lx, rx);
            if ((x + ly) % 4) a.pb(mx), b.pb(ly - 1);
            else a.pb(mx), b.pb(ly + 1);
        }
        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 5000 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5000 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 159 ms 21956 KB Output is correct
10 Correct 12 ms 6996 KB Output is correct
11 Correct 68 ms 14200 KB Output is correct
12 Correct 16 ms 7788 KB Output is correct
13 Correct 40 ms 10252 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 178 ms 21968 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 5000 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5000 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 159 ms 21956 KB Output is correct
10 Correct 12 ms 6996 KB Output is correct
11 Correct 68 ms 14200 KB Output is correct
12 Correct 16 ms 7788 KB Output is correct
13 Correct 40 ms 10252 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 178 ms 21968 KB Output is correct
17 Incorrect 3 ms 4908 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 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 5000 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5000 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 159 ms 21956 KB Output is correct
10 Correct 12 ms 6996 KB Output is correct
11 Correct 68 ms 14200 KB Output is correct
12 Correct 16 ms 7788 KB Output is correct
13 Correct 40 ms 10252 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 178 ms 21968 KB Output is correct
17 Incorrect 3 ms 4908 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 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 5000 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5000 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 159 ms 21956 KB Output is correct
10 Correct 12 ms 6996 KB Output is correct
11 Correct 68 ms 14200 KB Output is correct
12 Correct 16 ms 7788 KB Output is correct
13 Correct 40 ms 10252 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 178 ms 21968 KB Output is correct
17 Incorrect 3 ms 4948 KB Tree @(199999, 3) appears more than once: for edges on positions 0 and 1
18 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 5000 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5000 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 159 ms 21956 KB Output is correct
10 Correct 12 ms 6996 KB Output is correct
11 Correct 68 ms 14200 KB Output is correct
12 Correct 16 ms 7788 KB Output is correct
13 Correct 40 ms 10252 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 178 ms 21968 KB Output is correct
17 Incorrect 429 ms 37952 KB Tree @(3, 3) appears more than once: for edges on positions 17579 and 17581
18 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 5000 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5008 KB Output is correct
7 Correct 3 ms 5000 KB Output is correct
8 Correct 3 ms 5004 KB Output is correct
9 Correct 159 ms 21956 KB Output is correct
10 Correct 12 ms 6996 KB Output is correct
11 Correct 68 ms 14200 KB Output is correct
12 Correct 16 ms 7788 KB Output is correct
13 Correct 40 ms 10252 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 178 ms 21968 KB Output is correct
17 Incorrect 3 ms 4908 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -