3562. 面向对象程序设计

单点时限: 3.0 sec

内存限制: 1024 MB

在面向对象程序设计中,常常会运用到函数的扩展与重写。当一个类继承某个类的时候,它可以调用所有父类可以调用的函数。它可以声明新的函数。当新的函数签名与父类的某个函数一致时,就会发生函数的覆盖(重写)。所以,在子类的实例调用某个函数时,它会调用最近的父类(有可能是它自己)的那个函数实现。

这里我们不考虑访问权限等情况,我们只关心某个类在调用某个函数时,这个函数是在哪个类中实现的。

输入格式

输入具有如下格式:

$n \
p_2 \ p_3 \ \ldots \ p_n \
t_1 \ a_{11} \ a_{12} \ \ldots \ a_{1t_1} \
t_2 \ a_{21} \ a_{22} \ \ldots \ a_{2t_2} \
\vdots \
t_n \ a_{n1} \ a_{n2} \ \ldots \ a_{nt_n} \
q \
u_1 \ r_1 \
u_2 \ r_2 \
\vdots \
u_q \ r_q$

解释与数据规模约定:

  • $n$ 表示有 $n$ 个类,这些类从 $1$ 到 $n$ 编号。$2 \le n \le 10^5$。
  • $p_i$ 表示第 $i$ 个类的父类编号。$1 \le p_i \le i - 1$。第 $1$ 个类是所有类共同的祖先类,这个类没有父类。
  • $t_i$ 表示在第 $i$ 个类中定义了多少个函数,$a_{i1}, a_{i2}, \ldots, a_{it_i}$ 表示第 $i$ 个类中的函数列表。同一个类的函数列表中不会出现两个相同的函数。$1 \le a_{ij} \le 10^6$。$0 \le t_i \le 10^6, \sum t_i \le 10^6$。
  • $q$ 表示询问个数。$1 \le q \le 10^5$。
  • $u_i, r_i$ 表示第 $i$ 个询问,询问第 $u_i$ 个类的实例在调用 $r_i$ 函数时,调用的是哪个类中的版本。$1 \le u_i \le n, 1 \le r_i \le 10^6$。

输出格式

对于每个询问,输出答案。如果调用不合法(会导致编译错误),输出 $-1$。

样例

Input
5
1 2 3 3
2 2 1
0
2 5 2
2 4 5
1 5
4
3 4
5 2
4 5
1 3
Output
-1
3
4
-1

提示

样例等价于下面的 Java 代码。

class Class1 {
    void function2() { System.out.println("1"); }
    void function1() { System.out.println("1"); }
}

class Class2 extends Class1 {

}

class Class3 extends Class2 {
    void function5() { System.out.println("3"); }
    void function2() { System.out.println("3"); }
}

class Class4 extends Class3 {
    void function4() { System.out.println("4"); }
    void function5() { System.out.println("4"); }
}

class Class5 extends Class3 {
    void function5() { System.out.println("5"); }
}

void test() {
    new Class3().function4();
    new Class5().function2();
    new Class4().function5();
    new Class1().function3();
}

87 人解决,236 人已尝试。

114 份提交通过,共有 1376 份提交。

5.6 EMB 奖励。

创建: 2 年,5 月前.

修改: 2 年,5 月前.

最后提交: 1 月,4 周前.

来源: 2018 华东师范大学校赛

题目标签