oj.uz

Submission #53555

# Submission time Handle Problem Language Result Execution time Memory
53555 2018-06-30T08:00:05 Z !?!?(#2015) Regions (IOI09_regions) C++11
100 / 100
 7122 ms 67152 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 262144;
int N, R, Q;
int p[MAXN], c[MAXN]; // parent, color
vector<int> people[MAXN]; // people base on color
vector<int> child[MAXN]; // child of orig vertex

int dfsorder[MAXN]; // dfs order of orig vertex
int endinter[MAXN]; // end itnerval of orig vertex
int dfsorderinv[MAXN]; // dfs order inverse array

int dfs(int a)
{
    static int tp = 0;
    ++tp;
    
    dfsorder[a] = tp;
    dfsorderinv[tp] = a;
    
    for(auto x: child[a])
        dfs(x);
    endinter[a] = tp;
}

namespace Q1 //type 1 query: small parent, heavy child
{
    vector<int> pos[MAXN]; //position based on color
    void init()
    {
        for(int i=1; i<=N; ++i)
            pos[c[dfsorderinv[i]]].push_back(i);
    }
    int query(int r1, int r2)
    {
        //for each r1 interv, count
        int ans = 0;
        for(auto x: people[r1])
        {
            int s = dfsorder[x];
            int e = endinter[x];
            ans += upper_bound(pos[r2].begin(), pos[r2].end(), e)
                 - lower_bound(pos[r2].begin(), pos[r2].end(), s);
        }
        return ans;
    }
}
namespace Q2 //type 2 query: heavy parent, small child
{
    vector<int> pos[MAXN]; //position
    vector<int> acc[MAXN]; //accumulated
    void init()
    {
        for(int i=1; i<=R; ++i)
        {
            vector<pair<int, int> > V;
            for(auto x: people[i])
            {
                V.emplace_back(dfsorder[x], +1);
                V.emplace_back(endinter[x]+1, -1);
            }
            sort(V.begin(), V.end());
            pos[i].push_back(-1);
            acc[i].push_back(0);
            for(auto t: V)
            {
                pos[i].push_back(t.first);
                acc[i].push_back(acc[i][acc[i].size()-1] + t.second);
            }
        }
    }
    int query(int r1, int r2)
    {
        int ans = 0;
        for(auto x: people[r2])
        {
            int ind = lower_bound(pos[r1].begin(), pos[r1].end(), dfsorder[x]+1)
                    - pos[r1].begin() - 1;
            ans += acc[r1][ind];
        }
        return ans;
    }
}

void init()
{
    dfs(1); //we've done dfs ordering
    Q1::init();
    Q2::init();
}



int query(int r1, int r2)
{
    if(people[r1].size() < people[r2].size()) return Q1::query(r1, r2);
    else return Q2::query(r1, r2);    
}

int main()
{
    scanf("%d%d%d", &N, &R, &Q);
    scanf("%d", c+1);
    people[c[1]].push_back(1);
    for(int i=2; i<=N; ++i)
    {
        scanf("%d%d", p+i, c+i);
        people[c[i]].push_back(i);
        child[p[i]].push_back(i);
    }
    init();
    map<pair<int, int>, int> M;
    for(int i=0; i<Q; ++i)
    {
        int a, b; scanf("%d%d", &a, &b);
        if(M.find(make_pair(a, b)) == M.end())
            M[make_pair(a, b)] = query(a, b);
        printf("%d\n", M[make_pair(a, b)]);
        fflush(stdout);
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int dfs(int)':
regions.cpp:24:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
regions.cpp: In function 'int main()':
regions.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &R, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", c+1);
     ~~~~~^~~~~~~~~~~
regions.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", p+i, c+i);
         ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:115:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d%d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31004 KB Output is correct
2 Correct 30 ms 31028 KB Output is correct
3 Correct 34 ms 31064 KB Output is correct
4 Correct 34 ms 31212 KB Output is correct
5 Correct 36 ms 31240 KB Output is correct
6 Correct 38 ms 31596 KB Output is correct
7 Correct 46 ms 31696 KB Output is correct
8 Correct 46 ms 31764 KB Output is correct
9 Correct 74 ms 32296 KB Output is correct
10 Correct 117 ms 32712 KB Output is correct
11 Correct 147 ms 33140 KB Output is correct
12 Correct 193 ms 34072 KB Output is correct
13 Correct 279 ms 34072 KB Output is correct
14 Correct 475 ms 34748 KB Output is correct
15 Correct 390 ms 37028 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1500 ms 39528 KB Output is correct
2 Correct 1939 ms 39528 KB Output is correct
3 Correct 2609 ms 43660 KB Output is correct
4 Correct 354 ms 43660 KB Output is correct
5 Correct 513 ms 43660 KB Output is correct
6 Correct 709 ms 43660 KB Output is correct
7 Correct 972 ms 43660 KB Output is correct
8 Correct 1331 ms 46396 KB Output is correct
9 Correct 2609 ms 54440 KB Output is correct
10 Correct 5604 ms 60236 KB Output is correct
11 Correct 7122 ms 60236 KB Output is correct
12 Correct 2023 ms 60236 KB Output is correct
13 Correct 2784 ms 60236 KB Output is correct
14 Correct 3747 ms 60236 KB Output is correct
15 Correct 5172 ms 63624 KB Output is correct
16 Correct 5382 ms 67152 KB Output is correct
17 Correct 4572 ms 67152 KB Output is correct