oj.uz

Submission #521609

# Submission time Handle Problem Language Result Execution time Memory
521609 2022-02-02T14:36:35 Z andrei_boaca Regions (IOI09_regions) C++14
45 / 100
 3324 ms 85164 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][505],down[25005][505];
ll special[505][505];
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])
    {
        dfs(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 3 ms 6088 KB Output is correct
3 Correct 5 ms 6088 KB Output is correct
4 Correct 9 ms 6088 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 23 ms 6216 KB Output is correct
7 Correct 32 ms 6216 KB Output is correct
8 Correct 31 ms 6340 KB Output is correct
9 Correct 27 ms 6856 KB Output is correct
10 Correct 94 ms 6856 KB Output is correct
11 Correct 116 ms 7308 KB Output is correct
12 Correct 139 ms 8016 KB Output is correct
13 Correct 168 ms 7624 KB Output is correct
14 Correct 168 ms 8392 KB Output is correct
15 Correct 279 ms 12400 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1161 ms 13060 KB Output isn't correct
2 Incorrect 1246 ms 11684 KB Output isn't correct
3 Incorrect 1676 ms 15788 KB Output isn't correct
4 Correct 214 ms 8512 KB Output is correct
5 Correct 217 ms 10944 KB Output is correct
6 Incorrect 902 ms 23964 KB Output isn't correct
7 Correct 1131 ms 11544 KB Output is correct
8 Incorrect 999 ms 38736 KB Output isn't correct
9 Correct 1643 ms 19432 KB Output is correct
10 Correct 2509 ms 26244 KB Output is correct
11 Correct 2145 ms 19264 KB Output is correct
12 Incorrect 1139 ms 51632 KB Output isn't correct
13 Incorrect 1470 ms 52348 KB Output isn't correct
14 Incorrect 2667 ms 59760 KB Output isn't correct
15 Incorrect 2563 ms 76344 KB Output isn't correct
16 Incorrect 2552 ms 85164 KB Output isn't correct
17 Incorrect 3324 ms 73396 KB Output isn't correct