oj.uz

Submission #198706

# Submission time Handle Problem Language Result Execution time Memory
198706 2020-01-27T12:36:31 Z SamAnd Regions (IOI09_regions) C++17
100 / 100
 7798 ms 35068 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14312 KB Output is correct
2 Correct 16 ms 14460 KB Output is correct
3 Correct 19 ms 14456 KB Output is correct
4 Correct 23 ms 14456 KB Output is correct
5 Correct 22 ms 14456 KB Output is correct
6 Correct 30 ms 14968 KB Output is correct
7 Correct 40 ms 14712 KB Output is correct
8 Correct 71 ms 14840 KB Output is correct
9 Correct 97 ms 15352 KB Output is correct
10 Correct 99 ms 15484 KB Output is correct
11 Correct 110 ms 15608 KB Output is correct
12 Correct 224 ms 16120 KB Output is correct
13 Correct 154 ms 15660 KB Output is correct
14 Correct 161 ms 15868 KB Output is correct
15 Correct 289 ms 17656 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1069 ms 18116 KB Output is correct
2 Correct 1241 ms 17016 KB Output is correct
3 Correct 1311 ms 19448 KB Output is correct
4 Correct 283 ms 16760 KB Output is correct
5 Correct 523 ms 17912 KB Output is correct
6 Correct 1000 ms 18168 KB Output is correct
7 Correct 1317 ms 19832 KB Output is correct
8 Correct 1397 ms 23980 KB Output is correct
9 Correct 2278 ms 27000 KB Output is correct
10 Correct 3017 ms 30124 KB Output is correct
11 Correct 2971 ms 27768 KB Output is correct
12 Correct 4113 ms 28660 KB Output is correct
13 Correct 5355 ms 28584 KB Output is correct
14 Correct 7798 ms 28692 KB Output is correct
15 Correct 5665 ms 32108 KB Output is correct
16 Correct 5299 ms 35068 KB Output is correct
17 Correct 5419 ms 34752 KB Output is correct