oj.uz

Submission #53457

# Submission time Handle Problem Language Result Execution time Memory
53457 2018-06-30T05:12:59 Z !?!?(#2015) Regions (IOI09_regions) C++11
75 / 100
 8000 ms 47192 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
{
    void init()
    {
    
    }
}

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 Q1::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:69:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
regions.cpp: In function 'int main()':
regions.cpp:73: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:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", c+1);
     ~~~~~^~~~~~~~~~~
regions.cpp:78: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:86: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 21 ms 18764 KB Output is correct
2 Correct 20 ms 18868 KB Output is correct
3 Correct 20 ms 18956 KB Output is correct
4 Correct 19 ms 19116 KB Output is correct
5 Correct 25 ms 19196 KB Output is correct
6 Correct 28 ms 19196 KB Output is correct
7 Correct 44 ms 19208 KB Output is correct
8 Correct 49 ms 19380 KB Output is correct
9 Correct 93 ms 19804 KB Output is correct
10 Correct 97 ms 20084 KB Output is correct
11 Correct 124 ms 20460 KB Output is correct
12 Correct 177 ms 21232 KB Output is correct
13 Correct 209 ms 21232 KB Output is correct
14 Correct 330 ms 21684 KB Output is correct
15 Correct 473 ms 23924 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1812 ms 25780 KB Output is correct
2 Correct 2044 ms 25780 KB Output is correct
3 Correct 2946 ms 29616 KB Output is correct
4 Correct 320 ms 29616 KB Output is correct
5 Correct 368 ms 29616 KB Output is correct
6 Correct 533 ms 29616 KB Output is correct
7 Correct 918 ms 29616 KB Output is correct
8 Correct 1712 ms 31760 KB Output is correct
9 Correct 3678 ms 37608 KB Output is correct
10 Correct 6356 ms 43324 KB Output is correct
11 Correct 6818 ms 43324 KB Output is correct
12 Correct 7909 ms 43324 KB Output is correct
13 Execution timed out 8042 ms 43324 KB Time limit exceeded
14 Execution timed out 8034 ms 43324 KB Time limit exceeded (wall clock)
15 Execution timed out 8029 ms 43324 KB Time limit exceeded
16 Execution timed out 7540 ms 47160 KB Time limit exceeded (wall clock)
17 Execution timed out 7757 ms 47192 KB Time limit exceeded (wall clock)