Submission #672228

#	Time	Username	Problem	Language	Result	Execution time	Memory
672228		Hanksburger	Regions (IOI09_regions)	C++17	100 / 100	2392 ms	50944 KiB

regions

#include <bits/stdc++.h>
using namespace std;
vector<int> child[200005], vec[25005], ans[25005][2], tmp;
vector<pair<int, pair<int, bool> > > tt[25005];
int a[200005][2], region[200005];
vector<pair<int, bool> > t;
void dfs(int u)
{
    a[u][0]=t.size();
    t.push_back({u, 0});
    for (int v:child[u])
        dfs(v);
    a[u][1]=t.size();
    t.push_back({u, 1});
}
int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    for (int i=1; i<=n; i++)
    {
        if (i>1)
        {
            int x;
            cin >> x;
            child[x].push_back(i);
        }
        cin >> region[i];
        vec[region[i]].push_back(i);
    }
    dfs(1);
    for (int i=1; i<=m; i++)
    {
        for (int u:vec[i])
        {
            tt[i].push_back({a[u][0], {u, 0}});
            tt[i].push_back({a[u][1], {u, 1}});
        }
        sort(tt[i].begin(), tt[i].end());
    }
    for (int i=1; i<=m; i++)
    {
        if (vec[i].size()*vec[i].size()>n)
        {
            for (int j=0; j<=m; j++)
            {
                ans[i][0].push_back(0);
                ans[i][1].push_back(0);
            }
            int cur=0;
            for (int j=0; j<t.size(); j++)
            {
                if (region[t[j].first]==i)
                    cur+=1-t[j].second*2;
                else
                    ans[i][0][region[t[j].first]]+=cur*t[j].second;
            }
            tmp.clear();
            for (int j=0; j<t.size(); j++)
            {
                if (region[t[j].first]==i)
                    cur+=t[j].second;
                else if (t[j].second)
                {
                    ans[i][1][region[tmp[tmp.size()-1]]]+=cur;
                    cur+=tmp[tmp.size()-2];
                    tmp.pop_back();
                    tmp.pop_back();
                }
                else
                {
                    tmp.push_back(cur);
                    tmp.push_back(t[j].first);
                    cur=0;
                }
            }
        }
    }
    for (int i=1; i<=q; i++)
    {
        int x, y;
        cin >> x >> y;
        if (vec[x].size()*vec[x].size()>n)
            cout << ans[x][0][y] << '\n';
        else if (vec[y].size()*vec[y].size()>n)
            cout << ans[y][1][x] << '\n';
        else
        {
            int cur=0, ind=0, res=0;
            for (int j=0; j<tt[x].size(); j++)
            {
                while (ind<tt[y].size() && tt[y][ind].first<tt[x][j].first)
                    res+=cur*tt[y][ind++].second.second;
                cur+=1-tt[x][j].second.second*2;
            }
            while (ind<tt[y].size())
                res+=cur*tt[y][ind++].second.second;
            cout << res << '\n';
        }
        fflush(stdout);
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:43:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         if (vec[i].size()*vec[i].size()>n)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:51:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for (int j=0; j<t.size(); j++)
      |                           ~^~~~~~~~~
regions.cpp:59:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for (int j=0; j<t.size(); j++)
      |                           ~^~~~~~~~~
regions.cpp:83:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         if (vec[x].size()*vec[x].size()>n)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:85:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |         else if (vec[y].size()*vec[y].size()>n)
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:90:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, bool> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for (int j=0; j<tt[x].size(); j++)
      |                           ~^~~~~~~~~~~~~
regions.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, bool> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                 while (ind<tt[y].size() && tt[y][ind].first<tt[x][j].first)
      |                        ~~~^~~~~~~~~~~~~
regions.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, bool> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             while (ind<tt[y].size())
      |                    ~~~^~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85