oj.uz

Submission #53465

# Submission time Handle Problem Language Result Execution time Memory
53465 2018-06-30T05:28:47 Z !?!?(#2015) Regions (IOI09_regions) C++11
0 / 100
 6471 ms 67216 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 = upper_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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 31096 KB Output isn't correct
2 Incorrect 29 ms 31284 KB Output isn't correct
3 Incorrect 27 ms 31284 KB Output isn't correct
4 Incorrect 30 ms 31284 KB Output isn't correct
5 Incorrect 33 ms 31288 KB Output isn't correct
6 Incorrect 42 ms 31520 KB Output isn't correct
7 Incorrect 41 ms 31520 KB Output isn't correct
8 Incorrect 41 ms 31668 KB Output isn't correct
9 Incorrect 77 ms 32116 KB Output isn't correct
10 Incorrect 77 ms 32604 KB Output isn't correct
11 Incorrect 179 ms 33064 KB Output isn't correct
12 Incorrect 188 ms 33828 KB Output isn't correct
13 Incorrect 220 ms 33904 KB Output isn't correct
14 Incorrect 325 ms 34616 KB Output isn't correct
15 Incorrect 382 ms 36996 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1603 ms 39488 KB Output isn't correct
2 Incorrect 1555 ms 39488 KB Output isn't correct
3 Incorrect 2294 ms 43592 KB Output isn't correct
4 Incorrect 291 ms 43592 KB Output isn't correct
5 Incorrect 475 ms 43592 KB Output isn't correct
6 Incorrect 722 ms 43592 KB Output isn't correct
7 Incorrect 1014 ms 43592 KB Output isn't correct
8 Incorrect 1373 ms 46412 KB Output isn't correct
9 Incorrect 2702 ms 54320 KB Output isn't correct
10 Incorrect 4989 ms 60068 KB Output isn't correct
11 Incorrect 6471 ms 60068 KB Output isn't correct
12 Incorrect 1995 ms 60068 KB Output isn't correct
13 Incorrect 2465 ms 60068 KB Output isn't correct
14 Incorrect 3428 ms 60068 KB Output isn't correct
15 Incorrect 4602 ms 63736 KB Output isn't correct
16 Incorrect 4540 ms 67216 KB Output isn't correct
17 Incorrect 5106 ms 67216 KB Output isn't correct