Submission #198708

#	Time	Username	Problem	Language	Result	Execution time	Memory
198708		SamAnd	Regions (IOI09_regions)	C++11	100 / 100	6686 ms	35068 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 200005, R1 = 502;

int n, r, qq;
int p[N], u[N];
vector<int> a[N];

int ans[R1][R1];

int q[R1];
void dfs(int x)
{
    for (int i = 1; i <= r; ++i)
    {
        ans[i][u[x]] += q[i];
    }
    ++q[u[x]];
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        dfs(h);
    }
    --q[u[x]];
}

void solv1()
{
    dfs(1);
    while (qq--)
    {
        int e1, e2;
        scanf("%d%d", &e1, &e2);
        printf("%d\n", ans[e1][e2]);
        fflush(stdout);
    }
}

int tin[N], tout[N], ti;
void dfs1(int x)
{
    tin[x] = ++ti;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        dfs1(h);
    }
    tout[x] = ++ti;
}

vector<pair<int, bool> > v[N];
vector<int> vv[N];

void solv2()
{
    dfs1(1);
    for (int i = 1; i <= n; ++i)
    {
        v[u[i]].push_back(m_p(tin[i], true));
        v[u[i]].push_back(m_p(tout[i], false));
        vv[u[i]].push_back(tin[i]);
    }
    for (int i = 1; i <= r; ++i)
    {
        sort(v[i].begin(), v[i].end());
        sort(vv[i].begin(), vv[i].end());
    }
    while (qq--)
    {
        int e1, e2;
        scanf("%d%d", &e1, &e2);
        int ans = 0;
        int q = 0;
        int i = 0, j = 0;
        while (1)
        {
            if (i == v[e1].size() || j == vv[e2].size())
                break;
            if (v[e1][i].first < vv[e2][j])
            {
                if (v[e1][i].second)
                    ++q;
                else
                    --q;
                ++i;
            }
            else
            {
                ans += q;
                ++j;
            }
        }
        printf("%d\n", ans);
        fflush(stdout);
    }
}

int main()
{
    scanf("%d%d%d", &n, &r, &qq);
    scanf("%d", &u[1]);
    for (int i = 2; i <= n; ++i)
    {
        scanf("%d%d", &p[i], &u[i]);
        a[p[i]].push_back(i);
    }
    if (r <= 500)
        solv1();
    else
        solv2();
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfs1(int)':
regions.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'void solv2()':
regions.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (i == v[e1].size() || j == vv[e2].size())
                 ~~^~~~~~~~~~~~~~~
regions.cpp:78:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (i == v[e1].size() || j == vv[e2].size())
                                      ~~^~~~~~~~~~~~~~~~
regions.cpp: In function 'void solv1()':
regions.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &e1, &e2);
         ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void solv2()':
regions.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &e1, &e2);
         ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &r, &qq);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &u[1]);
     ~~~~~^~~~~~~~~~~~~
regions.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &p[i], &u[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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