oj.uz

Submission #521614

# Submission time Handle Problem Language Result Execution time Memory
521614 2022-02-02T14:42:56 Z andrei_boaca Regions (IOI09_regions) C++14
100 / 100
 2424 ms 122516 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<int> muchii[200005];
vector<int> members[25005];
vector<int> freq;
struct date
{
    int poz,add;
};
vector<date> ev[25005];
int nrm[25005];
int reg[200005];
int n,r,q;
int cnt=0;
int par[200005];
int up[25005][455],down[25005][455];
ll special[455][455];
bool isfr[25005];
int in[200005],out[200005],timp;
int f[25005];
int jos;
int nr[200005];
void dfs(int nod)
{
    timp++;
    in[nod]=timp;
    f[reg[nod]]++;
    for(int i:freq)
    {
        if(isfr[reg[nod]])
            special[nrm[i]][nrm[reg[nod]]]+=f[i];
        else
            up[reg[nod]][nrm[i]]+=f[i];
    }
    for(int i:muchii[nod])
        dfs(i);
    f[reg[nod]]--;
    timp++;
    out[nod]=timp;
}
void build(int nod)
{
    nr[nod]=(reg[nod]==jos);
    for(int i:muchii[nod])
    {
        build(i);
        nr[nod]+=nr[i];
    }
    down[reg[nod]][nrm[jos]]+=nr[nod];
}
bool comp(date a, date b)
{
    return a.poz<b.poz;
}
int main()
{
    cin>>n>>r>>q;
    cin>>reg[1];
    members[reg[1]].push_back(1);
    for(int i=2;i<=n;i++)
    {
        cin>>par[i];
        cin>>reg[i];
        muchii[par[i]].push_back(i);
        members[reg[i]].push_back(i);
    }
    for(int i=1;i<=r;i++)
    {
        if(members[i].size()>=500)
        {
            isfr[i]=1;
            freq.push_back(i);
            cnt++;
            nrm[i]=cnt;
        }
        else
            isfr[i]=0;
    }
    dfs(1);
    for(int i:freq)
    {
        jos=i;
        build(1);
    }
    for(int i=1;i<=r;i++)
    {
        for(int j:members[i])
        {
            ev[i].push_back({in[j]-1,-1});
            ev[i].push_back({out[j],+1});
        }
        sort(ev[i].begin(),ev[i].end(),comp);
    }
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(isfr[r1]&&isfr[r2])
        {
            cout<<special[nrm[r1]][nrm[r2]]<<endl;
            continue;
        }
        if(isfr[r1])
        {
            cout<<up[r2][nrm[r1]]<<endl;
            continue;
        }
        if(isfr[r2])
        {
            cout<<down[r1][nrm[r2]]<<endl;
            continue;
        }
        int j=0;
        int s=0;
        ll ans=0;
        for(date i:ev[r1])
        {
            while(j<ev[r2].size()&&ev[r2][j].poz<=i.poz)
                {
                    if(ev[r2][j].add==1)
                        s++;
                    j++;
                }
            ans+=s*i.add;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             while(j<ev[r2].size()&&ev[r2][j].poz<=i.poz)
      |                   ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 6 ms 6088 KB Output is correct
4 Correct 7 ms 6088 KB Output is correct
5 Correct 12 ms 6216 KB Output is correct
6 Correct 23 ms 6232 KB Output is correct
7 Correct 16 ms 6344 KB Output is correct
8 Correct 37 ms 6344 KB Output is correct
9 Correct 64 ms 6856 KB Output is correct
10 Correct 89 ms 6856 KB Output is correct
11 Correct 98 ms 7240 KB Output is correct
12 Correct 146 ms 7880 KB Output is correct
13 Correct 151 ms 7720 KB Output is correct
14 Correct 191 ms 8372 KB Output is correct
15 Correct 237 ms 11712 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 13436 KB Output is correct
2 Correct 898 ms 12296 KB Output is correct
3 Correct 1617 ms 16020 KB Output is correct
4 Correct 276 ms 8512 KB Output is correct
5 Correct 363 ms 10532 KB Output is correct
6 Correct 722 ms 34896 KB Output is correct
7 Correct 946 ms 11456 KB Output is correct
8 Correct 869 ms 53960 KB Output is correct
9 Correct 1696 ms 19136 KB Output is correct
10 Correct 2424 ms 24952 KB Output is correct
11 Correct 2347 ms 19208 KB Output is correct
12 Correct 1074 ms 77372 KB Output is correct
13 Correct 1339 ms 77820 KB Output is correct
14 Correct 1981 ms 91760 KB Output is correct
15 Correct 2150 ms 115640 KB Output is correct
16 Correct 2278 ms 122516 KB Output is correct
17 Correct 2411 ms 102864 KB Output is correct