oj.uz

Submission #53470

# Submission time Handle Problem Language Result Execution time Memory
53470 2018-06-30T05:33:28 Z !?!?(#2015) Regions (IOI09_regions) C++11
100 / 100
 6666 ms 67136 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 31 ms 31100 KB Output is correct
2 Correct 31 ms 31100 KB Output is correct
3 Correct 30 ms 31192 KB Output is correct
4 Correct 29 ms 31268 KB Output is correct
5 Correct 29 ms 31356 KB Output is correct
6 Correct 42 ms 31472 KB Output is correct
7 Correct 55 ms 31648 KB Output is correct
8 Correct 58 ms 31648 KB Output is correct
9 Correct 55 ms 32248 KB Output is correct
10 Correct 126 ms 32632 KB Output is correct
11 Correct 127 ms 33204 KB Output is correct
12 Correct 243 ms 34000 KB Output is correct
13 Correct 312 ms 34000 KB Output is correct
14 Correct 418 ms 34748 KB Output is correct
15 Correct 410 ms 37052 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 39760 KB Output is correct
2 Correct 1790 ms 39760 KB Output is correct
3 Correct 2542 ms 43644 KB Output is correct
4 Correct 290 ms 43644 KB Output is correct
5 Correct 450 ms 43644 KB Output is correct
6 Correct 557 ms 43644 KB Output is correct
7 Correct 875 ms 43644 KB Output is correct
8 Correct 1517 ms 46408 KB Output is correct
9 Correct 2307 ms 54504 KB Output is correct
10 Correct 4885 ms 60188 KB Output is correct
11 Correct 6666 ms 60188 KB Output is correct
12 Correct 2339 ms 60188 KB Output is correct
13 Correct 3306 ms 60188 KB Output is correct
14 Correct 3493 ms 60188 KB Output is correct
15 Correct 4398 ms 63660 KB Output is correct
16 Correct 4847 ms 67136 KB Output is correct
17 Correct 4061 ms 67136 KB Output is correct