oj.uz

Submission #100785

# Submission time Handle Problem Language Result Execution time Memory
100785 2019-03-14T11:24:00 Z Alexa2001 Regions (IOI09_regions) C++17
100 / 100
 2306 ms 39416 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14336 KB Output is correct
2 Correct 18 ms 14336 KB Output is correct
3 Correct 17 ms 14336 KB Output is correct
4 Correct 18 ms 14464 KB Output is correct
5 Correct 20 ms 14464 KB Output is correct
6 Correct 21 ms 14460 KB Output is correct
7 Correct 40 ms 14512 KB Output is correct
8 Correct 29 ms 14592 KB Output is correct
9 Correct 50 ms 14848 KB Output is correct
10 Correct 85 ms 14848 KB Output is correct
11 Correct 104 ms 15152 KB Output is correct
12 Correct 122 ms 15632 KB Output is correct
13 Correct 153 ms 15360 KB Output is correct
14 Correct 192 ms 16040 KB Output is correct
15 Correct 199 ms 17784 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 19288 KB Output is correct
2 Correct 835 ms 18420 KB Output is correct
3 Correct 1327 ms 20728 KB Output is correct
4 Correct 243 ms 16000 KB Output is correct
5 Correct 302 ms 17320 KB Output is correct
6 Correct 639 ms 17016 KB Output is correct
7 Correct 810 ms 18096 KB Output is correct
8 Correct 728 ms 22008 KB Output is correct
9 Correct 1319 ms 23124 KB Output is correct
10 Correct 1720 ms 26744 KB Output is correct
11 Correct 2306 ms 23072 KB Output is correct
12 Correct 795 ms 26352 KB Output is correct
13 Correct 1103 ms 26516 KB Output is correct
14 Correct 1317 ms 33084 KB Output is correct
15 Correct 1923 ms 30348 KB Output is correct
16 Correct 1866 ms 33532 KB Output is correct
17 Correct 1688 ms 39416 KB Output is correct