oj.uz

Submission #672209

# Submission time Handle Problem Language Result Execution time Memory
672209 2022-12-15T04:23:40 Z Hanksburger Regions (IOI09_regions) C++17
95 / 100
 8000 ms 44324 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;
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 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

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:65:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |         if (vec[x].size()*vec[x].size()>n)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:67:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |         else if (vec[y].size()*vec[y].size()>n)
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:84: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]
   84 |             for (int j=0; j<tt.size(); j++)
      |                           ~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6736 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 4 ms 6736 KB Output is correct
4 Correct 7 ms 6736 KB Output is correct
5 Correct 10 ms 6736 KB Output is correct
6 Correct 19 ms 6864 KB Output is correct
7 Correct 32 ms 6864 KB Output is correct
8 Correct 36 ms 6864 KB Output is correct
9 Correct 57 ms 7536 KB Output is correct
10 Correct 115 ms 7604 KB Output is correct
11 Correct 216 ms 7888 KB Output is correct
12 Correct 223 ms 8656 KB Output is correct
13 Correct 342 ms 8268 KB Output is correct
14 Correct 595 ms 8748 KB Output is correct
15 Correct 687 ms 12336 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2017 ms 13272 KB Output is correct
2 Correct 2322 ms 11984 KB Output is correct
3 Correct 5318 ms 15400 KB Output is correct
4 Correct 528 ms 8780 KB Output is correct
5 Correct 594 ms 11344 KB Output is correct
6 Correct 653 ms 14016 KB Output is correct
7 Correct 1316 ms 15768 KB Output is correct
8 Correct 1407 ms 26232 KB Output is correct
9 Correct 5849 ms 19368 KB Output is correct
10 Correct 4237 ms 44324 KB Output is correct
11 Execution timed out 8070 ms 18620 KB Time limit exceeded
12 Correct 2446 ms 20496 KB Output is correct
13 Correct 3561 ms 20828 KB Output is correct
14 Correct 3671 ms 23264 KB Output is correct
15 Correct 6096 ms 25408 KB Output is correct
16 Correct 6416 ms 32840 KB Output is correct
17 Correct 5681 ms 34388 KB Output is correct