Submission #672214

#	Time	Username	Problem	Language	Result	Execution time	Memory
672214		Hanksburger	Regions (IOI09_regions)	C++17	95 / 100	8054 ms	45244 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;
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++)
    {
        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 u:vec[i])
//                tmp.push_back(a[u][0]);
//            sort(tmp.begin(), tmp.end());
//            for (int j=1; j<=n; j++)
//            {
//                int x=lower_bound(tmp.begin(), tmp.end(), a[j][0])-tmp.begin();
//                int y=lower_bound(tmp.begin(), tmp.end(), a[j][1])-tmp.begin();
//                ans[i][1][region[j]]+=y-x;
//            }
        }
    }
    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
        {
            tt.clear();
            for (int u:vec[x])
            {
                tt.push_back({a[u][0], {u, 0}});
                tt.push_back({a[u][1], {u, 1}});
            }
            for (int u:vec[y])
            {
                tt.push_back({a[u][0], {u, 0}});
                tt.push_back({a[u][1], {u, 1}});
            }
            sort(tt.begin(), tt.end());
            int cur=0, res=0;
            for (int j=0; j<tt.size(); j++)
            {
                if (region[tt[j].second.first]==x)
                    cur+=1-tt[j].second.second*2;
                else
                    res+=cur*tt[j].second.second;
            }
            cout << res << '\n';
        }
        fflush(stdout);
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:34:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if (vec[i].size()*vec[i].size()>n)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:42: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]
   42 |             for (int j=0; j<t.size(); j++)
      |                           ~^~~~~~~~~
regions.cpp:50: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]
   50 |             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:102: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]
  102 |             for (int j=0; j<tt.size(); j++)
      |                           ~^~~~~~~~~~

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