oj.uz

Submission #53464

# Submission time Handle Problem Language Result Execution time Memory
53464 2018-06-30T05:27:42 Z !?!?(#2015) Regions (IOI09_regions) C++11
0 / 100
 6693 ms 67200 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 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 query(int, int)':
regions.cpp:98:1: warning: control reaches end of non-void function [-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 28 ms 31100 KB Output isn't correct
2 Incorrect 28 ms 31100 KB Output isn't correct
3 Incorrect 27 ms 31220 KB Output isn't correct
4 Incorrect 30 ms 31252 KB Output isn't correct
5 Incorrect 33 ms 31428 KB Output isn't correct
6 Incorrect 47 ms 31500 KB Output isn't correct
7 Incorrect 65 ms 31600 KB Output isn't correct
8 Incorrect 50 ms 31688 KB Output isn't correct
9 Incorrect 91 ms 32204 KB Output isn't correct
10 Incorrect 149 ms 32604 KB Output isn't correct
11 Incorrect 144 ms 33032 KB Output isn't correct
12 Incorrect 164 ms 33872 KB Output isn't correct
13 Incorrect 176 ms 33968 KB Output isn't correct
14 Incorrect 342 ms 34772 KB Output isn't correct
15 Incorrect 297 ms 37080 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1352 ms 39540 KB Output isn't correct
2 Incorrect 1754 ms 39540 KB Output isn't correct
3 Incorrect 2175 ms 43604 KB Output isn't correct
4 Incorrect 313 ms 43604 KB Output isn't correct
5 Incorrect 470 ms 43604 KB Output isn't correct
6 Incorrect 596 ms 43604 KB Output isn't correct
7 Incorrect 779 ms 43604 KB Output isn't correct
8 Incorrect 1210 ms 46472 KB Output isn't correct
9 Incorrect 2682 ms 54384 KB Output isn't correct
10 Incorrect 5015 ms 60124 KB Output isn't correct
11 Incorrect 6693 ms 60124 KB Output isn't correct
12 Incorrect 1886 ms 60124 KB Output isn't correct
13 Incorrect 2780 ms 60124 KB Output isn't correct
14 Incorrect 3079 ms 60124 KB Output isn't correct
15 Incorrect 4704 ms 63520 KB Output isn't correct
16 Incorrect 4577 ms 67200 KB Output isn't correct
17 Incorrect 4661 ms 67200 KB Output isn't correct