Submission #715642

#	Time	Username	Problem	Language	Result	Execution time	Memory
715642		Sorting	Fountain Parks (IOI21_parks)	C++17	0 / 100	13 ms	23816 KiB

parks

#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[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];

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;

        p1 = {sx + dy, sy + dx};
        p2 = {sx - dy, sy - dx};

        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;
                adj_2sat[v[i].first].push_back(v[j].second);
                rev_adj_2sat[v[j].second].push_back(v[i].first);
            }
        }
    }

    queue<int> q;
    for(int i = 0; i < 2 * (n - 1); ++i){
        cnt_out[i] = adj_2sat[i].size();
        if(!cnt_out[i])
            q.push(i);
    }

    vector<int> topsort;
    while(!q.empty()){
        int u = q.front();
        q.pop();

        topsort.push_back(u);

        for(int to: rev_adj_2sat[u]){
            --cnt_out[to];
            if(!cnt_out[to])
                q.push(to);
        }
    }

    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 (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30