oj.uz

답안 #715634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715634 2023-03-27T10:48:33 Z Sorting 분수 공원 (IOI21_parks) C++17
0 / 100
 12 ms 23808 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[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 = 1;
    for(auto [to, idx_e]: adj[u]){
        if(vis[to]) continue;
        cnt += dfs(to);
        active_edges.push_back(idx_e);        
    }
    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);
    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];

        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

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23808 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23808 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23808 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23808 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23808 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23808 KB Solution announced impossible, but it is possible.
2 Halted 0 ms 0 KB -