Submission #1017038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017038		amine_aroua	Plahte (COCI17_plahte)	C++17	160 / 160	294 ms	47904 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
int n , m;
vector<int> color;
vector<pair<int, int>> allX ,allY;
vector<tuple<int , int ,int ,int , int>> events;
vector<int> par;
vector<vector<int>> adj;
bool contained(int i , int j)
{
    i-- , j--;
    return (allX[j].first <= allX[i].first && allX[i].second <= allX[j].second && allY[j].first <= allY[i].first && allY[i].second <= allY[j].second);
}
vector<set<int>> nodes;
vector<int> ans;
void dfs(int x)
{
    nodes[x].insert(color[x]);
    for(auto u : adj[x])
    {
        dfs(u);
        if((int)nodes[u].size() > (int)nodes[x].size())
            swap(nodes[u] , nodes[x]);
        for(auto v : nodes[u])
            nodes[x].insert(v);
    }
    ans[x] = (int)nodes[x].size() - 1;
}
int main()
{
    cin>>n>>m;
    vector<int> compX , compY;
    par.assign(n + m + 1 , 0);
    color.assign(n + m + 1, 0);
    for(int i = 0 ; i < n ;i++)
    {
        int a , b , c , d;
        cin>>a>>c>>b>>d;
        allX.push_back({a , b});
        allY.push_back({c , d});
        events.push_back({a , 0 ,i+ 1, c , d});
        events.push_back({b , 1 ,i + 1, c , d});
    }
    for(int i = 0 ; i < m ; i++)
    {
        int a , b , k;
        cin>>a>>b>>k;
        color[i + n + 1] = k;
        allX.push_back({a , a});
        allY.push_back({b , b});
        events.push_back({a , 0 ,i+ 1 + n, b , b});
        events.push_back({a, 1 , i + 1 + n,b , b });
    }
    sort(events.begin() , events.end());
    set<pair<int ,int>> s;
    for(auto [x,strt, id , ly , hy ] : events)
    {
        if(strt == 1)
        {
            s.erase({ly , id});
            s.erase({hy , id});
        }
        else
        {
            auto it = s.lower_bound({ly , -1});
            if(it == s.end())
            {
                par[id] = 0;
            }
            else
            {
                auto his_id = it->second;
                if(contained(id , his_id))
                {
                    par[id] = his_id;
                }
                else
                    par[id] = par[his_id];
            }
            s.insert({ly , id});
            s.insert({hy , id});
        }
    }
    adj.assign(n + m + 1 , {});
    for(int i = 1 ; i <= n + m ; i++)
    {
        adj[par[i]].push_back(i);
    }
    ans.assign(n + m + 1 , 0);
    nodes.assign(n + m + 1 , set<int>());
    dfs(0);
    for(int i = 1 ; i <= n ; i++)
        cout<<ans[i]<<"\n";
}

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32