oj.uz

답안 #521613

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521613 2022-02-02T14:41:24 Z andrei_boaca Regions (IOI09_regions) C++14
95 / 100
 2485 ms 131076 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])
    {
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 12 ms 6216 KB Output is correct
6 Correct 25 ms 6216 KB Output is correct
7 Correct 24 ms 6216 KB Output is correct
8 Correct 29 ms 6344 KB Output is correct
9 Correct 53 ms 6864 KB Output is correct
10 Correct 99 ms 6856 KB Output is correct
11 Correct 108 ms 7240 KB Output is correct
12 Correct 129 ms 7960 KB Output is correct
13 Correct 145 ms 7624 KB Output is correct
14 Correct 205 ms 8392 KB Output is correct
15 Correct 261 ms 12328 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1034 ms 13776 KB Output is correct
2 Correct 996 ms 12504 KB Output is correct
3 Correct 1801 ms 16648 KB Output is correct
4 Correct 175 ms 8452 KB Output is correct
5 Correct 343 ms 10860 KB Output is correct
6 Correct 727 ms 37684 KB Output is correct
7 Correct 1104 ms 11576 KB Output is correct
8 Correct 971 ms 58904 KB Output is correct
9 Correct 1696 ms 19376 KB Output is correct
10 Correct 2485 ms 26156 KB Output is correct
11 Correct 2227 ms 19252 KB Output is correct
12 Correct 1095 ms 83352 KB Output is correct
13 Correct 1553 ms 84144 KB Output is correct
14 Correct 1889 ms 99224 KB Output is correct
15 Correct 2215 ms 126612 KB Output is correct
16 Runtime error 200 ms 131076 KB Execution killed with signal 9
17 Correct 2320 ms 113064 KB Output is correct