oj.uz

Submission #814465

# Submission time Handle Problem Language Result Execution time Memory
814465 2023-08-08T07:40:52 Z becaido Fountain Parks (IOI21_parks) C++17
5 / 100
 404 ms 44876 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;
    while (q.size()) {
        int pos = q.front();
        q.pop();
        if (pos == 0) break;
        u.pb(pos), v.pb(pa[pos]);
        if (--deg[pa[pos]] == 0) q.push(pa[pos]);
    }
    a.resize(n - 1), b.resize(n - 1);
    FOR (i, 0, n - 2) if (x[u[i]] == 2 && x[v[i]] == 2) {
        a[i] = x[u[i]] - 1;
        b[i] = (y[u[i]] + y[v[i]]) / 2;
    }
    FOR (i, 0, n - 2) if (x[u[i]] == 6 && x[v[i]] == 6) {
        a[i] = x[u[i]] + 1;
        b[i] = (y[u[i]] + y[v[i]]) / 2;
    }
    set<pair<int, int>> s;
    set<int> ys;
    vector<pair<int, int>> all;
    FOR (i, 0, n - 2) if (x[u[i]] != x[v[i]]) {
        all.pb(y[u[i]], i);
    }

    sort(all.begin(), all.end());
    for (auto [Y, i] : all) {
        int X = (x[u[i]] + y[u[i]]) / 2;
        Y--;
        if (ys.count(Y)) Y += 2;
        a[i] = X, b[i] = Y;
        ys.insert(b[i]);
        s.emplace(a[i], b[i]);
    }

    FOR (i, 0, n - 2) if (x[u[i]] == 4 && x[v[i]] == 4) {
        a[i] = x[u[i]] - 1, b[i] = (y[u[i]] + y[v[i]]) / 2;
        if (s.count({a[i], b[i]})) a[i] += 2;
        s.emplace(a[i], b[i]);
    }
    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 5004 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 143 ms 22128 KB Output is correct
10 Correct 12 ms 6868 KB Output is correct
11 Correct 59 ms 14380 KB Output is correct
12 Correct 16 ms 7784 KB Output is correct
13 Correct 38 ms 10400 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 142 ms 22156 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 5004 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 143 ms 22128 KB Output is correct
10 Correct 12 ms 6868 KB Output is correct
11 Correct 59 ms 14380 KB Output is correct
12 Correct 16 ms 7784 KB Output is correct
13 Correct 38 ms 10400 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 142 ms 22156 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5000 KB Output is correct
19 Incorrect 3 ms 4948 KB a[4] = 4 is not an odd integer
20 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 5004 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 143 ms 22128 KB Output is correct
10 Correct 12 ms 6868 KB Output is correct
11 Correct 59 ms 14380 KB Output is correct
12 Correct 16 ms 7784 KB Output is correct
13 Correct 38 ms 10400 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 142 ms 22156 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5000 KB Output is correct
19 Incorrect 3 ms 4948 KB a[4] = 4 is not an odd integer
20 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 5004 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 143 ms 22128 KB Output is correct
10 Correct 12 ms 6868 KB Output is correct
11 Correct 59 ms 14380 KB Output is correct
12 Correct 16 ms 7784 KB Output is correct
13 Correct 38 ms 10400 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 142 ms 22156 KB Output is correct
17 Incorrect 3 ms 4948 KB a[0] = 0 is not an odd integer
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 5004 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 143 ms 22128 KB Output is correct
10 Correct 12 ms 6868 KB Output is correct
11 Correct 59 ms 14380 KB Output is correct
12 Correct 16 ms 7784 KB Output is correct
13 Correct 38 ms 10400 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 142 ms 22156 KB Output is correct
17 Incorrect 404 ms 44876 KB Tree (a[0], b[0]) = (8793, 1) is not adjacent to edge between u[0]=2975 @(17584, 2) and v[0]=188724 @(17586, 2)
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 5004 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 143 ms 22128 KB Output is correct
10 Correct 12 ms 6868 KB Output is correct
11 Correct 59 ms 14380 KB Output is correct
12 Correct 16 ms 7784 KB Output is correct
13 Correct 38 ms 10400 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 142 ms 22156 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5000 KB Output is correct
19 Incorrect 3 ms 4948 KB a[4] = 4 is not an odd integer
20 Halted 0 ms 0 KB -