oj.uz

Submission #540146

# Submission time Handle Problem Language Result Execution time Memory
540146 2022-03-19T11:52:15 Z model_code Fliper (COCI22_fliper) C++17
110 / 110
 710 ms 138772 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 1000005;

int n, ok = 1;
int x[MAXN], y[MAXN], par[MAXN], siz[MAXN], bio[MAXN], sol[MAXN];
char c[MAXN];
vector <int> sazx, sazy, nodes, edges, lef, rig;
vector <pi> vx[MAXN], vy[MAXN], v[MAXN];

void dsu_init () {
    for (int i = 0; i <= 2*n; i++) {
        par[i] = i;
        siz[i] = 1;
    }
}

int nadi (int a) {
    if (a == par[a]) return a;
    return par[a] = nadi(par[a]);
}

void spoji (int a, int b) {
    a = nadi(a);
    b = nadi(b);
    if (a == b) return;
    if (a > b) swap(a, b);
    par[a] = b;
    siz[b] += siz[a];
}

void sazmi () {
    for (int i = 0; i < n; i++) {
        sazx.push_back(x[i]);
        sazy.push_back(y[i]);
    }
    sort(sazx.begin(), sazx.end());
    sort(sazy.begin(), sazy.end());
    sazx.erase(unique(sazx.begin(), sazx.end()), sazx.end());
    sazy.erase(unique(sazy.begin(), sazy.end()), sazy.end());
    for (int i = 0; i < n; i++) {
        x[i] = lower_bound(sazx.begin(), sazx.end(), x[i]) - sazx.begin();
        y[i] = lower_bound(sazy.begin(), sazy.end(), y[i]) - sazy.begin();
    }
}

void find_cycles () {
    for (int i = 0; i < n; i++) {
        if (c[i] == '/') {
            vx[x[i]].push_back({2 * y[i] + 1, 2 * i + 0});
            vx[x[i]].push_back({2 * y[i] + 0, 2 * i + 1});
            vy[y[i]].push_back({2 * x[i] + 0, 2 * i + 0});
            vy[y[i]].push_back({2 * x[i] + 1, 2 * i + 1});
        } else {
            vx[x[i]].push_back({2 * y[i] + 1, 2 * i + 0});
            vx[x[i]].push_back({2 * y[i] + 0, 2 * i + 1});
            vy[y[i]].push_back({2 * x[i] + 1, 2 * i + 0});
            vy[y[i]].push_back({2 * x[i] + 0, 2 * i + 1});
        }
    }
    for (int i = 0; i < sazx.size(); i++) {
        sort(vx[i].begin(), vx[i].end());
        for (int j = 1; j + 1 < vx[i].size(); j += 2) {
            spoji(vx[i][j].second, vx[i][j + 1].second);
        }
        spoji(vx[i][0].second, 2 * n);
        spoji(vx[i].back().second, 2 * n);
    }
    for (int i = 0; i < sazy.size(); i++) {
        sort(vy[i].begin(), vy[i].end());
        for (int j = 1; j + 1 < vy[i].size(); j += 2) {
            spoji(vy[i][j].second, vy[i][j + 1].second);
        }
        spoji(vy[i][0].second, 2 * n);
        spoji(vy[i].back().second, 2 * n);
    }
}

void build_graph () {
    for (int i = 0; i <= 2 * n; i++) {
        if (i == par[i]) {
            nodes.push_back(i);
            if (i < 2 * n && siz[i] % 8 != 0) ok = 0;
        }
    }
    for (int i = 0; i < n; i++) {
        int a = nadi(2 * i);
        int b = nadi(2 * i + 1);
        v[a].push_back({b, i});
        v[b].push_back({a, i});
    }
}

void euler (int x) {
    while (v[x].size()) {
        int to = v[x].back().first;
        int ind = v[x].back().second;
        v[x].pop_back();
        if (bio[ind]) continue;
        bio[ind] = 1;
        euler(to);
        edges.push_back(ind);
    }
}

void solve () {
    euler(2 * n);
    for (int i = 0; i < edges.size(); i++) {
        if (i % 2 == 0) lef.push_back(edges[i]);
        if (i % 2 == 1) rig.push_back(edges[i]);
    }
    edges.clear();
    memset(bio, 0, sizeof bio);

    for (auto i : lef) {
        int a = nadi(2 * i);
        int b = nadi(2 * i + 1);
        v[a].push_back({b, i});
        v[b].push_back({a, i});
    }
    for (int i = (int)nodes.size() - 1; i >= 0; i--) {
        euler(nodes[i]);
    }
    for (int i = 0; i < edges.size(); i++) {
        sol[edges[i]] = 3 + i % 2;
    }
    edges.clear();
    memset(bio, 0, sizeof bio);

    for (auto i : rig) {
        int a = nadi(2 * i);
        int b = nadi(2 * i + 1);
        v[a].push_back({b, i});
        v[b].push_back({a, i});
    }
    for (int i = (int)nodes.size() - 1; i >= 0; i--) {
        euler(nodes[i]);
    }
    for (int i = 0; i < edges.size(); i++) {
        sol[edges[i]] = 1 + i % 2;
    }
    edges.clear();
    memset(bio, 0, sizeof bio);
}

void ispis () {
    for (int i = 0; i < n; i++) {
        cout << sol[i] << " ";
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    dsu_init();
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> c[i];
    }
    sazmi();
    find_cycles();
    build_graph();
    if (!ok) {
        cout << "-1";
        return 0;
    }
    solve();
    ispis();
    return 0;
}

Compilation message

Main.cpp: In function 'void find_cycles()':
Main.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < sazx.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int j = 1; j + 1 < vx[i].size(); j += 2) {
      |                         ~~~~~~^~~~~~~~~~~~~~
Main.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < sazy.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int j = 1; j + 1 < vy[i].size(); j += 2) {
      |                         ~~~~~~^~~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 74644 KB Output is correct
2 Correct 39 ms 74844 KB Output is correct
3 Correct 35 ms 74624 KB Output is correct
4 Correct 36 ms 74708 KB Output is correct
5 Correct 32 ms 70736 KB Output is correct
6 Correct 35 ms 70696 KB Output is correct
7 Correct 35 ms 74652 KB Output is correct
8 Correct 41 ms 70740 KB Output is correct
9 Correct 34 ms 74648 KB Output is correct
10 Correct 35 ms 70748 KB Output is correct
11 Correct 35 ms 74696 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 137844 KB Output is correct
2 Correct 532 ms 137052 KB Output is correct
3 Correct 520 ms 135236 KB Output is correct
4 Correct 442 ms 131076 KB Output is correct
5 Correct 365 ms 126260 KB Output is correct
6 Correct 380 ms 125356 KB Output is correct
7 Correct 450 ms 128660 KB Output is correct
8 Correct 377 ms 126968 KB Output is correct
9 Correct 35 ms 70740 KB Output is correct
10 Correct 363 ms 124952 KB Output is correct
11 Correct 34 ms 70732 KB Output is correct
12 Correct 44 ms 74704 KB Output is correct
13 Correct 35 ms 70868 KB Output is correct
14 Correct 37 ms 74708 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 74644 KB Output is correct
2 Correct 39 ms 74844 KB Output is correct
3 Correct 35 ms 74624 KB Output is correct
4 Correct 36 ms 74708 KB Output is correct
5 Correct 32 ms 70736 KB Output is correct
6 Correct 35 ms 70696 KB Output is correct
7 Correct 35 ms 74652 KB Output is correct
8 Correct 41 ms 70740 KB Output is correct
9 Correct 34 ms 74648 KB Output is correct
10 Correct 35 ms 70748 KB Output is correct
11 Correct 35 ms 74696 KB Output is correct
12 Correct 625 ms 137844 KB Output is correct
13 Correct 532 ms 137052 KB Output is correct
14 Correct 520 ms 135236 KB Output is correct
15 Correct 442 ms 131076 KB Output is correct
16 Correct 365 ms 126260 KB Output is correct
17 Correct 380 ms 125356 KB Output is correct
18 Correct 450 ms 128660 KB Output is correct
19 Correct 377 ms 126968 KB Output is correct
20 Correct 35 ms 70740 KB Output is correct
21 Correct 363 ms 124952 KB Output is correct
22 Correct 34 ms 70732 KB Output is correct
23 Correct 44 ms 74704 KB Output is correct
24 Correct 35 ms 70868 KB Output is correct
25 Correct 37 ms 74708 KB Output is correct
26 Correct 710 ms 138772 KB Output is correct
27 Correct 680 ms 136804 KB Output is correct
28 Correct 592 ms 135484 KB Output is correct
29 Correct 544 ms 131224 KB Output is correct
30 Correct 439 ms 126572 KB Output is correct
31 Correct 456 ms 125628 KB Output is correct
32 Correct 518 ms 129676 KB Output is correct
33 Correct 448 ms 127944 KB Output is correct
34 Correct 437 ms 119940 KB Output is correct
35 Correct 399 ms 118576 KB Output is correct
36 Correct 492 ms 119768 KB Output is correct
37 Correct 39 ms 70900 KB Output is correct
38 Correct 433 ms 124776 KB Output is correct
39 Correct 36 ms 70804 KB Output is correct
40 Correct 37 ms 74644 KB Output is correct
41 Correct 34 ms 70800 KB Output is correct
42 Correct 35 ms 74680 KB Output is correct