Submission #1099365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099365		Zero_OP	Drawing (CEOI22_drawing)	C++14	100 / 100	150 ms	38596 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], ptr;
point points[MAX];
vector<int> adj[MAX], on;
 
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 dfs(int u){
   // cout << u << '\n';
    for(int v : adj[u]){
        answer[on[ptr++]] = v;
        dfs(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();
 
    for(int i = 1; i <= n; ++i){
        if(i != id) on.push_back(i);
    }
 
    predfs(r);
    root_of_points = r;
    sort(all(on), comparator);
    answer[id] = r;

    ptr = 0;
    dfs(r);
 
    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:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(filename".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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