Submission #100785

#	Time	Username	Problem	Language	Result	Execution time	Memory
100785		Alexa2001	Regions (IOI09_regions)	C++17	100 / 100	2306 ms	39416 KiB

regions

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5, B = 500, Rmax = 25005;
typedef long long ll;

int n, R, Q, tmp;
int reg[Nmax], t[Nmax], cnt[Rmax];
int up[Nmax], down[Nmax], code[Nmax];
ll val1[Nmax / B + 5][Rmax], val2[Nmax / B + 5][Rmax];

vector<int> v[Nmax], In[Nmax], Out[Nmax];

void dfs(int node = 1)
{
  //  In[node] = ++tmp;
    In[reg[node]].push_back(++tmp);

    for(auto it : v[node]) dfs(it);

  //  Out[node] = tmp;
    Out[reg[node]].push_back(tmp);
}

void calc1(int R)
{
    int i;
    for(i=1; i<=n; ++i)
    {
        up[i] = up[t[i]] + (reg[i] == R);
        val1[code[R]][reg[i]] += up[i];
    }
}

void calc2(int R)
{
    int i;
    for(i=n; i; --i)
    {
        down[i] = (reg[i] == R);
        for(auto it : v[i]) down[i] += down[it];
        val2[code[R]][reg[i]] += down[i];
    }
}

void precalc()
{
    dfs();

    int i, Nrcodes = 0;
    for(i=1; i<=n; ++i) ++cnt[reg[i]];

    for(i=1; i<=R; ++i)
        if(cnt[i] > B)
        {
            code[i] = ++Nrcodes;
            calc1(i);
            calc2(i);
        }
}

int query(int x, int y)
{
    if(cnt[x] > B) return val1[code[x]][y];
    if(cnt[y] > B) return val2[code[y]][x];

    int i = 0, ans = 0;

    for(auto it : In[x])
    {
        while(i < In[y].size() && In[y][i] <= it) ++i;
        ans -= i;
    }

    i = 0;
    for(auto it : Out[x])
    {
        while(i < In[y].size() && In[y][i] <= it) ++i;
        ans += i;
    }
    return ans;
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n >> R >> Q >> reg[1];

    int i, x, y;
    for(i=2; i<=n; ++i)
    {
        cin >> t[i] >> reg[i];
        v[t[i]].push_back(i);
    }

    precalc();

    while(Q--)
    {
        cin >> x >> y;
        cout << query(x, y) << endl;
    }

    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int query(int, int)':
regions.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < In[y].size() && In[y][i] <= it) ++i;
               ~~^~~~~~~~~~~~~~
regions.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < In[y].size() && In[y][i] <= it) ++i;
               ~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85