oj.uz

Submission #715653

# Submission time Handle Problem Language Result Execution time Memory
715653 2023-03-27T12:07:47 Z Sorting Fountain Parks (IOI21_parks) C++17
5 / 100
 702 ms 124788 KB 
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;

map<pair<int, int>, int> f;
vector<pair<int, int>> adj[N];
bool vis[2 * N];
vector<int> active_edges;

map<pair<int, int>, vector<pair<int, int>>> for_2sat;
array<pair<int, int>, 2> pts[N];

vector<int> adj_2sat[2 * N], rev_adj_2sat[2 * N];
int cnt_out[2 * N];
vector<int> topsort;

void dfs_topsort(int u){
    vis[u] = true;

    for(auto to: adj_2sat[u]){
        if(vis[to]) continue;
        dfs_topsort(to);
    }
    topsort.push_back(u);
}

int dfs(int u){
    vis[u] = true;
    int cnt = 0;
    for(auto [to, idx_e]: adj[u]){
        if(vis[to]) continue;
        cnt += dfs(to);
        active_edges.push_back(idx_e);
        // cerr << idx_e << " idx_e" << endl;
        ++cnt;   
    }
    return cnt;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n = x.size();
    for(int i = 0; i < n; ++i)
        f[{x[i], y[i]}] = i;

    vector<array<int, 2>> edges;
    for(int i = 0; i < n; ++i){
        array<int, 2> adj_dir[2]{{2, 0}, {0, 2}};
        for(auto [dx, dy]: adj_dir){
            auto [to_x, to_y] = pair{dx + x[i], dy + y[i]};
            if(f.count({to_x, to_y})){
                int idx = f[{to_x, to_y}];
                edges.push_back({i, idx});
                adj[i].push_back({idx, edges.size() - 1});
                adj[idx].push_back({i, edges.size() - 1});
            }
        }
    }

    int cnt = dfs(0);
    // cerr << cnt << " cnt" << endl;
    if(cnt != n - 1)
        return 0;


    for(int i = 0; i < n - 1; ++i){
        int idx_e = active_edges[i];

        pair<int, int> p1, p2;
        int f1 = edges[idx_e][0];
        int f2 = edges[idx_e][1];
        // cerr << f1 << " " << f2 << " edge" << endl;

        auto [sx, sy] = pair{x[f1], y[f1]};
        auto [dx, dy] = pair{x[f2] - x[f1], y[f2] - y[f1]};
        dx /= 2;
        dy /= 2;

        if(dx < 0 || dy < 0){
            sx += dx;
            dy += dy;
            dx = -dx;
            dy = -dy;
        }

        if(dx == 1){
            p1 = {sx + 1, sy + 1};
            p2 = {sx + 1, sy - 1};
        }
        else{
            p1 = {sx + 1, sy + 1};
            p2 = {sx - 1, sy + 1};
        }

        // cerr << p1.first << " " << p1.second << " p1" << endl;
        // cerr << p2.first << " " << p2.second << " p2" << endl;

        pts[i] = {p1, p2};
        for_2sat[p1].push_back({2 * i, 2 * i + 1});
        for_2sat[p2].push_back({2 * i + 1, 2 * i});
    }

    for(auto [p, v]: for_2sat){
        for(int i = 0; i < v.size(); ++i){
            for(int j = 0; j < v.size(); ++j){
                if(i == j) continue;
                // cerr << "edge " << v[i].first << " " << v[j].second << endl;
                adj_2sat[v[i].first].push_back(v[j].second);
                rev_adj_2sat[v[j].second].push_back(v[i].first);
            }
        }
    }

    for(int i = 0; i < 2 * (n - 1); ++i)
        vis[i] = false;

    for(int i = 0; i < 2 * (n - 1); ++i)
        if(!vis[i])
            dfs_topsort(i);

    // cerr << topsort.size() << " topsort size" << endl;
    // for(int x: topsort)
        // cerr << x << " ";
    // cerr << endl;
    
    if(topsort.size() != 2 * (n - 1))
        return 0;

    static int loc[2 * N];
    reverse(topsort.begin(), topsort.end());
    for(int i = 0; i < 2 * (n - 1); ++i)
        loc[topsort[i]] = i;

    vector<pair<int, int>> benches;
    for(int i = 0; i < (n - 1); ++i){
        if(loc[2 * i] < loc[2 * i + 1])
            benches.push_back(pts[i][0]);
        else
            benches.push_back(pts[i][1]);
    }

    vector<int> u, v, a, b;
    for(int i = 0; i < n - 1; ++i){
        int idx_e = active_edges[i];
        u.push_back(edges[idx_e][0]);
        v.push_back(edges[idx_e][1]);
        a.push_back(benches[i].first);
        b.push_back(benches[i].second);
    }

    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i = 0; i < v.size(); ++i){
      |                        ~~^~~~~~~~~~
parks.cpp:107:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             for(int j = 0; j < v.size(); ++j){
      |                            ~~^~~~~~~~~~
parks.cpp:128:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  128 |     if(topsort.size() != 2 * (n - 1))
      |        ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23804 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23744 KB Output is correct
9 Correct 283 ms 73624 KB Output is correct
10 Correct 32 ms 28876 KB Output is correct
11 Correct 117 ms 50776 KB Output is correct
12 Correct 40 ms 31304 KB Output is correct
13 Correct 46 ms 31428 KB Output is correct
14 Correct 16 ms 23892 KB Output is correct
15 Correct 14 ms 23976 KB Output is correct
16 Correct 277 ms 71072 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23804 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23744 KB Output is correct
9 Correct 283 ms 73624 KB Output is correct
10 Correct 32 ms 28876 KB Output is correct
11 Correct 117 ms 50776 KB Output is correct
12 Correct 40 ms 31304 KB Output is correct
13 Correct 46 ms 31428 KB Output is correct
14 Correct 16 ms 23892 KB Output is correct
15 Correct 14 ms 23976 KB Output is correct
16 Correct 277 ms 71072 KB Output is correct
17 Incorrect 13 ms 23764 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23804 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23744 KB Output is correct
9 Correct 283 ms 73624 KB Output is correct
10 Correct 32 ms 28876 KB Output is correct
11 Correct 117 ms 50776 KB Output is correct
12 Correct 40 ms 31304 KB Output is correct
13 Correct 46 ms 31428 KB Output is correct
14 Correct 16 ms 23892 KB Output is correct
15 Correct 14 ms 23976 KB Output is correct
16 Correct 277 ms 71072 KB Output is correct
17 Incorrect 13 ms 23764 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23804 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23744 KB Output is correct
9 Correct 283 ms 73624 KB Output is correct
10 Correct 32 ms 28876 KB Output is correct
11 Correct 117 ms 50776 KB Output is correct
12 Correct 40 ms 31304 KB Output is correct
13 Correct 46 ms 31428 KB Output is correct
14 Correct 16 ms 23892 KB Output is correct
15 Correct 14 ms 23976 KB Output is correct
16 Correct 277 ms 71072 KB Output is correct
17 Incorrect 13 ms 23764 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 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23804 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23744 KB Output is correct
9 Correct 283 ms 73624 KB Output is correct
10 Correct 32 ms 28876 KB Output is correct
11 Correct 117 ms 50776 KB Output is correct
12 Correct 40 ms 31304 KB Output is correct
13 Correct 46 ms 31428 KB Output is correct
14 Correct 16 ms 23892 KB Output is correct
15 Correct 14 ms 23976 KB Output is correct
16 Correct 277 ms 71072 KB Output is correct
17 Incorrect 702 ms 124788 KB Tree @(3, 100001) appears more than once: for edges on positions 41208 and 41209
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23812 KB Output is correct
6 Correct 12 ms 23804 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23744 KB Output is correct
9 Correct 283 ms 73624 KB Output is correct
10 Correct 32 ms 28876 KB Output is correct
11 Correct 117 ms 50776 KB Output is correct
12 Correct 40 ms 31304 KB Output is correct
13 Correct 46 ms 31428 KB Output is correct
14 Correct 16 ms 23892 KB Output is correct
15 Correct 14 ms 23976 KB Output is correct
16 Correct 277 ms 71072 KB Output is correct
17 Incorrect 13 ms 23764 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -