oj.uz

Submission #1099264

# Submission time Handle Problem Language Result Execution time Memory
1099264 2024-10-11T03:44:10 Z Zero_OP Drawing (CEOI22_drawing) C++14
15 / 100
 1500 ms 55404 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 23912 KB Output is correct
2 Execution timed out 1528 ms 55404 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7000 KB Output is correct
2 Correct 236 ms 12112 KB Output is correct
3 Correct 271 ms 22128 KB Output is correct
4 Correct 592 ms 7256 KB Output is correct
5 Correct 304 ms 7764 KB Output is correct
6 Correct 10 ms 7004 KB Output is correct
7 Correct 146 ms 7112 KB Output is correct
8 Correct 10 ms 7004 KB Output is correct
9 Correct 468 ms 17068 KB Output is correct
10 Correct 157 ms 13648 KB Output is correct
11 Correct 502 ms 7304 KB Output is correct
12 Correct 314 ms 7508 KB Output is correct
13 Correct 10 ms 7004 KB Output is correct
14 Correct 147 ms 7128 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7000 KB Output is correct
2 Correct 236 ms 12112 KB Output is correct
3 Correct 271 ms 22128 KB Output is correct
4 Correct 592 ms 7256 KB Output is correct
5 Correct 304 ms 7764 KB Output is correct
6 Correct 10 ms 7004 KB Output is correct
7 Correct 146 ms 7112 KB Output is correct
8 Correct 10 ms 7004 KB Output is correct
9 Correct 468 ms 17068 KB Output is correct
10 Correct 157 ms 13648 KB Output is correct
11 Correct 502 ms 7304 KB Output is correct
12 Correct 314 ms 7508 KB Output is correct
13 Correct 10 ms 7004 KB Output is correct
14 Correct 147 ms 7128 KB Output is correct
15 Correct 16 ms 8092 KB Output is correct
16 Execution timed out 1552 ms 36180 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7000 KB Output is correct
2 Correct 236 ms 12112 KB Output is correct
3 Correct 271 ms 22128 KB Output is correct
4 Correct 592 ms 7256 KB Output is correct
5 Correct 304 ms 7764 KB Output is correct
6 Correct 10 ms 7004 KB Output is correct
7 Correct 146 ms 7112 KB Output is correct
8 Correct 10 ms 7004 KB Output is correct
9 Correct 468 ms 17068 KB Output is correct
10 Correct 157 ms 13648 KB Output is correct
11 Correct 502 ms 7304 KB Output is correct
12 Correct 314 ms 7508 KB Output is correct
13 Correct 10 ms 7004 KB Output is correct
14 Correct 147 ms 7128 KB Output is correct
15 Correct 16 ms 8092 KB Output is correct
16 Execution timed out 1552 ms 36180 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 23912 KB Output is correct
2 Execution timed out 1528 ms 55404 KB Time limit exceeded
3 Halted 0 ms 0 KB -