oj.uz

Submission #1026970

# Submission time Handle Problem Language Result Execution time Memory
1026970 2024-07-18T15:48:32 Z Summers Regions (IOI09_regions) C++14
100 / 100
 3369 ms 120808 KB 
#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<long long> v[1000000],d[1000000], ans[1000000],c[1000000];
long long t=1, p[1000000], tin[1000000], tout[1000000];
void dfs(long long vr)
{
    tin[vr]=t++;
    d[p[vr]].push_back(tin[vr]);
    for (int i=0;i<v[vr].size();i++)
    {
        dfs(v[vr][i]);
    }
    tout[vr]=t;
}

void dfs1(long long br, long long vr,long long val)
{
    if(val==p[vr])br++;
    else ans[val][p[vr]]+=br;

    for(int i=0;i<v[vr].size();i++)
    {
        dfs1(br, v[vr][i], val);
    }
}

int main()
{
    long long i,j,r,q,n,h,s,a,b;

    cin>>n>>r>>q;

    cin>>h;
    p[1]=h;
    c[h].push_back(1);

    for(i=2;i<=n;i++)
    {
        cin>>s>>h;
        p[i]=h;
        v[s].push_back(i);
        c[h].push_back(i);
    }
    dfs(1);

    for(i=1;i<=r;i++)
    {
        if(d[i].size()>=1000)
        {
            ans[i].resize(r+1);
            dfs1(0,1,i);
        }
    }

    while(q--)
    {
        cin>>a>>b;

        if(d[a].size()>=1000)
        {
            cout<<ans[a][b]<<endl;
            cout.flush();
        }
        else
        {
            long long an=0;
            for (long long i=0;i<c[a].size();i++)
            {
                auto it1 = upper_bound(d[b].begin(), d[b].end(), tout[c[a][i]]-1);
                it1--;
                auto it2 =lower_bound(d[b].begin(), d[b].end(), tin[c[a][i]]);

                an+=it1-it2+1;
            }

            cout<<an<<endl;
            cout.flush();
        }
    }
}

Compilation message

regions.cpp: In function 'void dfs(long long int)':
regions.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i=0;i<v[vr].size();i++)
      |                  ~^~~~~~~~~~~~~
regions.cpp: In function 'void dfs1(long long int, long long int, long long int)':
regions.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[vr].size();i++)
      |                 ~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:68:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for (long long i=0;i<c[a].size();i++)
      |                                ~^~~~~~~~~~~~
regions.cpp:30:17: warning: unused variable 'j' [-Wunused-variable]
   30 |     long long i,j,r,q,n,h,s,a,b;
      |                 ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 94296 KB Output is correct
2 Correct 20 ms 94296 KB Output is correct
3 Correct 20 ms 94296 KB Output is correct
4 Correct 21 ms 94296 KB Output is correct
5 Correct 23 ms 94248 KB Output is correct
6 Correct 27 ms 94296 KB Output is correct
7 Correct 33 ms 94296 KB Output is correct
8 Correct 36 ms 94388 KB Output is correct
9 Correct 37 ms 94808 KB Output is correct
10 Correct 67 ms 94956 KB Output is correct
11 Correct 94 ms 95576 KB Output is correct
12 Correct 113 ms 96188 KB Output is correct
13 Correct 158 ms 95948 KB Output is correct
14 Correct 204 ms 96600 KB Output is correct
15 Correct 212 ms 99416 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1571 ms 100676 KB Output is correct
2 Correct 1766 ms 99776 KB Output is correct
3 Correct 2123 ms 102776 KB Output is correct
4 Correct 215 ms 96592 KB Output is correct
5 Correct 286 ms 98384 KB Output is correct
6 Correct 1020 ms 98900 KB Output is correct
7 Correct 1301 ms 100456 KB Output is correct
8 Correct 957 ms 106064 KB Output is correct
9 Correct 1736 ms 108152 KB Output is correct
10 Correct 3329 ms 112668 KB Output is correct
11 Correct 3369 ms 108880 KB Output is correct
12 Correct 1201 ms 110008 KB Output is correct
13 Correct 1562 ms 110292 KB Output is correct
14 Correct 2086 ms 112348 KB Output is correct
15 Correct 2568 ms 114464 KB Output is correct
16 Correct 2501 ms 119528 KB Output is correct
17 Correct 2368 ms 120808 KB Output is correct