Submission #872368

#	Time	Username	Problem	Language	Result	Execution time	Memory
872368		abysmal	Drawing (CEOI22_drawing)	C++14	15 / 100	1565 ms	524288 KiB

Main

#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
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 35
• Subtask 5: 0 / 25