oj.uz

Submission #672228

# Submission time Handle Problem Language Result Execution time Memory
672228 2022-12-15T06:27:38 Z Hanksburger Regions (IOI09_regions) C++17
100 / 100
 2392 ms 50944 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7248 KB Output is correct
2 Correct 4 ms 7248 KB Output is correct
3 Correct 5 ms 7248 KB Output is correct
4 Correct 9 ms 7248 KB Output is correct
5 Correct 10 ms 7376 KB Output is correct
6 Correct 24 ms 7376 KB Output is correct
7 Correct 28 ms 7504 KB Output is correct
8 Correct 29 ms 7504 KB Output is correct
9 Correct 54 ms 8144 KB Output is correct
10 Correct 84 ms 8272 KB Output is correct
11 Correct 109 ms 8724 KB Output is correct
12 Correct 117 ms 9536 KB Output is correct
13 Correct 128 ms 9468 KB Output is correct
14 Correct 199 ms 10392 KB Output is correct
15 Correct 261 ms 14680 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 15408 KB Output is correct
2 Correct 1043 ms 14008 KB Output is correct
3 Correct 1407 ms 18500 KB Output is correct
4 Correct 151 ms 10344 KB Output is correct
5 Correct 232 ms 12508 KB Output is correct
6 Correct 681 ms 16164 KB Output is correct
7 Correct 838 ms 18456 KB Output is correct
8 Correct 1050 ms 30900 KB Output is correct
9 Correct 1591 ms 23624 KB Output is correct
10 Correct 2123 ms 50944 KB Output is correct
11 Correct 2277 ms 24312 KB Output is correct
12 Correct 968 ms 25728 KB Output is correct
13 Correct 1331 ms 26248 KB Output is correct
14 Correct 1604 ms 30100 KB Output is correct
15 Correct 2234 ms 32216 KB Output is correct
16 Correct 2392 ms 41308 KB Output is correct
17 Correct 2260 ms 42968 KB Output is correct