Submission #1099264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099264		Zero_OP	Drawing (CEOI22_drawing)	C++14	15 / 100	1552 ms	55404 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

using ll = long long;
using ld = long double;

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

struct point{
    int x, y;
    point(int x = 0, int y = 0) : x(x), y(y) {}

    friend istream& operator >> (istream& in, point& p){ return in >> p.x >> p.y; }
};

ll cross(const point& a, const point& b, const point& c){
    ll x1 = b.x - a.x, x2 = c.x - a.x;
    ll y1 = b.y - a.y, y2 = c.y - a.y;
    return x1 * y2 - x2 * y1;
}

bool ccw(const point& a, const point& b, const point& c){
    return cross(a, b, c) > 0;
}

const int MAX = 2e5 + 5;

int n, answer[MAX];
point points[MAX];
vector<int> adj[MAX];

int sz[MAX];

int predfs(int u){
    sz[u] = 1;
    for(int v : adj[u]){
        adj[v].erase(find(all(adj[v]), u));
        sz[u] += predfs(v);
    }
    return sz[u];
}

int select_root(){
    for(int i = 1; i <= n; ++i){
        if(sz(adj[i]) < 3){
            return i;
        }
    }
    assert(false);
}

int select_point(){
    int best = 1;
    for(int i = 2; i <= n; ++i){
        if(points[best].x > points[i].x || (points[best].x == points[i].x && points[best].y > points[i].y)){
            best = i;
        }
    }

    return best;
}

int root_of_points;
bool comparator(int u, int v){
    return ccw(points[root_of_points], points[u], points[v]);
}

void solve(int u, int last_id, vector<int>& id_points){
    if(sz(adj[u]) == 0) return;

    root_of_points = last_id;
    sort(all(id_points), comparator);

    if(sz(adj[u]) == 1){
        int v = adj[u][0], nxt = id_points.back();
        answer[nxt] = v;
        id_points.pop_back();
        solve(v, nxt, id_points);
    } else{
        int v1 = adj[u][1];
        int v2 = adj[u][0];

        vector<int> left_id_points, right_id_points;
        for(int i = 0; i < sz[v1]; ++i){
            left_id_points.push_back(id_points[i]);
        }

        for(int i = sz[v1]; i < sz[u] - 1; ++i){
            right_id_points.push_back(id_points[i]);
        }

        int nxt1 = left_id_points.back();
        int nxt2 = right_id_points.back();
        answer[nxt1] = v1;
        answer[nxt2] = v2;

        left_id_points.pop_back();
        right_id_points.pop_back();

        solve(v1, nxt1, left_id_points);
        solve(v2, nxt2, right_id_points);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= n; ++i){
        cin >> points[i];
    }

    int r = select_root();
    int id = select_point();

    vector<int> on;
    for(int i = 1; i <= n; ++i){
        if(i != id) on.push_back(i);
    }

    assert(predfs(r) == n);
    answer[id] = r;
    solve(r, id, on);

    for(int i = 1; i <= n; ++i){
        cout << answer[i] << ' ';
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool minimize(T&, const T&)':
Main.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
Main.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
Main.cpp: In function 'bool maximize(T&, const T&)':
Main.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(a < b) return a = b, true; return false;
      |     ^~
Main.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
Main.cpp: In function 'int main()':
Main.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 35
• Subtask 5: 0 / 25