oj.uz

Submission #872368

# Submission time Handle Problem Language Result Execution time Memory
872368 2023-11-13T02:36:55 Z abysmal Drawing (CEOI22_drawing) C++14
15 / 100
 1500 ms 524288 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>
#include<string.h>

using namespace std;

const double PI = (double) atan(1.0) * 4;
const double epsi = (double) 1e-3;
const int64_t INF = (int64_t) 3 * 1e9 + 777;
const int64_t mINF = (int64_t) 1e4;
const int64_t MOD = 1e9 + 7;
const int64_t MOD2 = 998244353;
const int nbit = 30;
const int ndig = 10;
const int nchar = 26;
const int B = 1000;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};
const int Dk = 8;
int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1};
int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2};

struct Point
{
    int64_t x;
    int64_t y;
    int id;
    Point(int64_t x_, int64_t y_, int id_) : x(x_), y(y_), id(id_) {}

    Point operator + (const Point& o) const { return Point(x + o.x, y + o.y, id); }
    Point operator - (const Point& o) const { return Point(x - o.x, y - o.y, id); }

    int64_t dot(const Point& o) const { return 1LL * x * o.x + 1LL * y * o.y; }
    int64_t cross(const Point& o) const { return 1LL * x * o.y - 1LL * o.x * y; }

//    Point rotate(double a) const
//    {
//        a = a * PI / 180.0;
//        return Point(x * cos(a) - y * sin(a), x * sin(a) - y * cos(a));
//    }

    bool operator < (const Point& o) const
    {
        if(x == o.x) return y < o.y;
        return x < o.x;
    }

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

    friend ostream& operator << (ostream& os, Point& p)
    {
        return os << fixed << setprecision(3) << "(" << p.x << "," << p.y << "," << p.id << ")";
    }
};

int sgn(double x)
{
    return (x > 0) - (x < 0);
}

int64_t orient(Point& a, Point& b, Point& c)
{
    return (b - a).cross(c - a);
}

bool parallel(Point a, Point b)
{
    return a.cross(b) == 0;
}

bool boundingBox(Point& a, Point& b, Point& c, Point& d)
{
    if(max(a.x, b.x) < min(c.x, d.x)) return false;
    if(max(a.y, b.y) < min(c.y, d.y)) return false;

    if(max(c.x, d.x) < min(a.x, b.x)) return false;
    if(max(c.y, d.y) < min(a.y, b.y)) return false;
    return true;
}

bool intersect(Point a, Point b, Point c, Point d)
{
    if(parallel(b - a, d - c))
    {
        if(orient(a, b, c) != 0) return false;
        if(!boundingBox(a, b, c, d)) return false;
        return true;
    }

    for(int t = 0; t < 2; t++)
    {
        int t1 = sgn(orient(a, b, c));
        int t2 = sgn(orient(a, b, d));
        if(sgn(t1) == sgn(t2) && t1 != 0) return false;
        swap(a, c); swap(b, d);
    }
    return true;
}

struct Solution
{
    int n;
    vector<int> a;
    vector<Point> p;
    vector<bool> used;
    vector<int> subtree;
    vector<vector<int> > order;
    vector<vector<int> > adj;
    Solution() {}

    void solve()
    {
        cin >> n;
        used.resize(n, 0);
        subtree.resize(n, 1);
        a.resize(n, -1);
        adj.resize(n);
        p.resize(n, Point(0, 0, 0));
        for(int i = 0; i < n - 1; i++)
        {
            int u;
            int v;
            cin >> u >> v;
            u--; v--;

            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        for(int i = 0; i < n; i++)
        {
            cin >> p[i];
            p[i].id = i;
        }

        DFS();
        DFS2(p);
        for(int i = 0; i < n; i++)
        {
            cout << a[i] + 1 << " ";
        }
    }

    void DFS2(vector<Point> t, int u = 0, int pr = -1)
    {
        sort(t.begin(), t.end());

        a[t[0].id] = u;
        Point o = t[0];
        reverse(t.begin(), t.end()); t.pop_back();
        sort(t.begin(), t.end(), [&](Point& t1, Point& t2)
         {
             return orient(o, t1, t2) > 0;
         });
         int k = 0;
        for(int i = 0; i < (int) adj[u].size(); i++)
        {
            int v = adj[u][i];
            if(v == pr) continue;

            vector<Point> nx;
            for(int j = 0; j < subtree[v]; j++)
            {
                nx.push_back(t[k + j]);
            }
            DFS2(nx, v, u);
            k += subtree[v];
        }
    }

    void DFS(int u = 0, int pr = -1)
    {
        for(int i = 0; i < (int) adj[u].size(); i++)
        {
            int v = adj[u][i];
            if(v == pr) continue;

            DFS(v, u);
            subtree[u] += subtree[v];
        }
    }

    int modadd(int t1, int t2)
    {
        int res = t1 + t2;
        if(res >= MOD) res -= MOD;
        return res;
    }

    int modsub(int t1, int t2)
    {
        int res = t1 - t2;
        if(res < 0) res += MOD;
        return res;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return res % MOD;
    }

    int64_t Abs(int64_t t1)
    {
        if(t1 < 0) return -t1;
        return t1;
    }

    int MASK(int j)
    {
        return (1 << j);
    }

    bool BIT(int t1, int j)
    {
        return (t1 & MASK(j));
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __setup();

    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 74048 KB Output is correct
2 Runtime error 770 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2908 KB Output is correct
2 Correct 354 ms 127120 KB Output is correct
3 Correct 235 ms 53632 KB Output is correct
4 Correct 924 ms 353584 KB Output is correct
5 Correct 707 ms 274000 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct
7 Correct 215 ms 59088 KB Output is correct
8 Correct 11 ms 3164 KB Output is correct
9 Correct 668 ms 256288 KB Output is correct
10 Correct 301 ms 109676 KB Output is correct
11 Correct 739 ms 276564 KB Output is correct
12 Correct 458 ms 125576 KB Output is correct
13 Correct 8 ms 2140 KB Output is correct
14 Correct 380 ms 97552 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2908 KB Output is correct
2 Correct 354 ms 127120 KB Output is correct
3 Correct 235 ms 53632 KB Output is correct
4 Correct 924 ms 353584 KB Output is correct
5 Correct 707 ms 274000 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct
7 Correct 215 ms 59088 KB Output is correct
8 Correct 11 ms 3164 KB Output is correct
9 Correct 668 ms 256288 KB Output is correct
10 Correct 301 ms 109676 KB Output is correct
11 Correct 739 ms 276564 KB Output is correct
12 Correct 458 ms 125576 KB Output is correct
13 Correct 8 ms 2140 KB Output is correct
14 Correct 380 ms 97552 KB Output is correct
15 Correct 19 ms 5612 KB Output is correct
16 Execution timed out 1565 ms 516060 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 2908 KB Output is correct
2 Correct 354 ms 127120 KB Output is correct
3 Correct 235 ms 53632 KB Output is correct
4 Correct 924 ms 353584 KB Output is correct
5 Correct 707 ms 274000 KB Output is correct
6 Correct 10 ms 2652 KB Output is correct
7 Correct 215 ms 59088 KB Output is correct
8 Correct 11 ms 3164 KB Output is correct
9 Correct 668 ms 256288 KB Output is correct
10 Correct 301 ms 109676 KB Output is correct
11 Correct 739 ms 276564 KB Output is correct
12 Correct 458 ms 125576 KB Output is correct
13 Correct 8 ms 2140 KB Output is correct
14 Correct 380 ms 97552 KB Output is correct
15 Correct 19 ms 5612 KB Output is correct
16 Execution timed out 1565 ms 516060 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 74048 KB Output is correct
2 Runtime error 770 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -