oj.uz

Submission #1017038

# Submission time Handle Problem Language Result Execution time Memory
1017038 2024-07-08T18:36:38 Z amine_aroua Plahte (COCI17_plahte) C++17
160 / 160
 294 ms 47904 KB 
#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.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 15268 KB Output is correct
2 Correct 88 ms 16044 KB Output is correct
3 Correct 0 ms 600 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 17124 KB Output is correct
2 Correct 103 ms 16668 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 30956 KB Output is correct
2 Correct 168 ms 27352 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 47904 KB Output is correct
2 Correct 294 ms 44480 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 46632 KB Output is correct
2 Correct 294 ms 45260 KB Output is correct
3 Correct 1 ms 344 KB Output is correct