Virtual Judge Weekly Game 2//First half of the 2023 school year-update~ I’ll do it for you tomorrow

• A-is here again

Problem Statement:

We have a rooted tree with N vertices numbered 11 to N. Vertex 11 is the root, and the parent of vertex i is vertex Pi?.
There are N coins with heads and tails, one on each vertex.
Additionally, there are N buttons numbered 11 to N. Pressing button n flips all coins on the vertices in the subtree rooted at vertex n.

Process Q queries described below.

In the i-th query, you are given a vertex set of size Mi?: ={,1,,2,…,,}Si?={vi,1?,vi,2?,…,vi,Mi? ?}.
Now, the coins on the vertices in Si? are facing heads-up, and the others are facing tails-up. In order to make all N coins face tails-up by repeatedly choosing a button and pressing it, at least how many button presses are needed? Print the answer, or ?1?1 if there is no way to make all the coins face tails-up.

Constraints

• 2≤N≤2×10e+5
• 1≤Pi?/*i is the subscript*/
• 1≤Q≤2×10e+5
• 1≤Mi?/*i is a subscript*/
• /*Q is above the summation head*/∑?/*i is equal to 1 below the summation*/Mi?/*i subscript*/≤2×10e + 5
• 1≤vi,j/*i,j are all subscripts*/?≤N
• vi,1?,vi,2?,…,vi/*subscript*/,Mi/*secondary subscript*/ are pairwise different.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N Q
P2? P3? … PN?
M1? v1,1? v1,2? ...... v1,M1/*1 is the second-level subscript*/
M2? v2,1? v2,2? …… v2,M2
?
MQ? vQ,1? vQ,2? …… vQ,MQ

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample 1

Inputcopy	Outputcopy
6 6 1 1 2 2 5 6 1 2 3 4 5 6 3 2 5 6 1 3 3 1 2 3 3 4 5 6 4 2 3 4 5	1 2 1 3 2 3

For the first query, you can satisfy the requirement in one button press, which is the minimum needed, as follows.

• Press button 11, flipping the coins on vertices 1,2,3,4,5,61,2,3,4,5,6.

For the second query, you can satisfy the requirement in two button presses, which is the minimum needed, as follows.

• Press button 44, flipping the coin on vertex 44.
• Press button 22, flipping the coins on vertex 2,4,5,62,4,5,6.

Sponsor

#include<bits/stdc + + .h>
using namespace std;

• B-nervous

Problem Statement:

Today, Osama gave Fadi an integer X, and Fadi was wondering about the minimum possible value of max(a,b) such that LCM(a,b) equals X. Both a and b should be positive integers.

LCM(a,b) is the smallest positive integer that is divisible by both a and b. For example, LCM(6,8)=24, LCM(4,12)=12, LCM(2,3)=6.

Of course, Fadi immediately knew the answer. Can you be just like Fadi and find any such pair?

Input

The first and only line contains an integer X (1≤X≤10e + 12).

Output

Print two positive integers, a and b, such that the value of max(a,b) is minimum possible and LCM(a,b) equals X. If there are several possible such pairs, you can print any.

Sample 1

Inputcopy	Outputcopy
2	1 2

Sample 2

Inputcopy	Outputcopy
6	2 3

Sample 3

Inputcopy	Outputcopy
4	1 4

Sample 4

Inputcopy	Outputcopy
1	1 1

Sponsor

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
//This part is to introduce the required header files and define some constants and type aliases.
bool is_prim(ll x) {
ll m = sqrt(x);
for (ll i = 2; i <= m; i + + ) {
if (x % i == 0)
return false;
}
return true;
}
/*
This is a function used to determine whether a number is prime.
It determines whether x is divisible by traversing the numbers between 2 and sqrt(x),
If it is divisible, return false.
Otherwise return true. The variable m is used internally to store the square root of x.
*/
ll gcd(ll a, ll b) {
if(b==0)
return a;
else
return gcd(b, a % b);
}
//This is a function that finds the greatest common divisor of two numbers. It uses recursion to implement the Euclidean algorithm.
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
ll x; cin >> x;
if (is_prim(x))
cout << "1 " << x << endl;
else {
ll maxn = 0;
for (ll i = 1; i <= sqrt(x); i + + ) {
if (x % i == 0) {
if (gcd(i, x / i) == 1)
maxn = i;
}
}
if(maxn)
cout << min(x / maxn, maxn) << " " << max(x / maxn, maxn) << endl;
else
cout << "1 " << x << endl;
}
return 0;
}
/*
In the main function, first read in a number x. If x is a prime number, "1 x" is output, indicating that the least common multiple is 1 and has no other common factors. Otherwise, you need to traverse all numbers i from 1 to sqrt(x) to find the largest i that satisfies the following conditions: i is a factor of x and gcd(i, x/i)=1.

Then, based on the found maximum factor maxn, output min(x/maxn, maxn) and max(x/maxn, maxn), which are the least common multiple of the two common factors.

Finally, according to the topic requirements, std::ios::sync_with_stdio(false) is used to improve the efficiency of input and output.
*/

#include<bits/stdc + + .h>
using namespace std;
// Calculate the greatest common divisor of two numbers
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// Calculate the least common multiple of two numbers
int lcm(int a, int b) {
    int gcdValue = gcd(a, b);
    return (a * b) / gcdValue;
}
int main(){
int X,q[1e + 12 + 10]
cin>>X;
int j=0;
for(int i=1;i<=X;i + + ){
if(X%i==0){
j + + ;
q[j]=i;
}
}
int tmp,ans;
for(int i=1;i<=j;i + + )
for(int k=i;k<=j;k + + )
{
if(lcm(i,j)==X)
{
if(max(i,j)

• C-again

Problem Statement:

There are 2N integers A1?,A2?,...,A2N? written on a blackboard, and an integer M at least 2.
Alice and Bob will play a game. They will alternately perform the following operation, with Alice going first, until there is no number on the blackboard.

• Choose a number and delete it from the blackboard.

At the end of the game, if the sum of numbers deleted by Alice modulo M equals the sum of numbers deleted by Bob modulo M, Bob wins; otherwise, Alice wins.
Which player will win if both plays optimally?

Constraints

• 1≤N≤2×105
• 2≤M≤109
• 0≤Ai/*i is the subscript */?≤M?1
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
A1? A2? … A2N?

Output

If Alice wins, print Alice; if Bob wins, print Bob.

Sample 1

Inputcopy	Outputcopy
2 9 1 4 8 5	Alice

The game may proceed as follows.

• Alice deletes 11.
• Bob deletes 44.
• Alice deletes 55.
• Bob deletes 88.

In this case, the sum of numbers deleted by Alice modulo M is (1 + 5)mod9=6(1 + 5)mod9=6, and the sum of numbers deleted by Bob modulo M is (4 + 8)mod9=3 (4 + 8)mod9=3. Since 6≠3, Alice wins.

Sample 2

Inputcopy	Outputcopy
3 998244353 1 2 3 1 2 3	Bob

• D-exciting//look

Elf by LadyofHats via Wikimedia Commons, public domain

As a huge fan of the popular collectible card game Numinous Wilds: the Elven Reign Chronicles (NWERC), you have a large collection of cards which you carefully organize by their rarity. One day you notice that someone has touched your collection, and that some of the cards are now out of order. The most natural suspect, of course, is your little brother Billy, who was absolutely 100 0% forbidden from playing with your cards. After a few minutes of interrogation Billy confesses that he indeed took a few consecutive cards from the middle of the stack, but he swears that he put them back in exactly the same order as they were. You suspect that Billy, being so young, may have simply mistakenly reversed the order of the cards that he took. Now you want to check your theory and decide if you can find the batch of cards that Billy took to play with.

//The core is in the following lines:

Is it possible to restore the order of the cards into non-decreasing order of their rarity by reversing just one contiguous batch of cards?

//Flip a certain section in the middle so that it does not decrease

Input

The input consists of:

• One line containing an integer n (1≤n≤10e + 6), the number of cards in your collection.
• One line containing n integers v1,…,vn (1≤vi≤10e + 9 for all i), the current order of the cards' rarity values.

Output

If the cards can be sorted by reversing exactly one contiguous subsequence of the list, then output the 11-based start and end indices of such a subsequence. Otherwise, output "impossible". If there are multiple valid solutions you may output any one of them.

Sample 1

Inputcopy	Outputcopy
7 10 13 19 19 15 14 20	3 6

Sample 2

Inputcopy	Outputcopy
6 9 1 8 2 7 3	impossible

Sample 3

Inputcopy	Outputcopy
3 1 2 3	1 1

Sponsor

• E-Look

Problem Statement:

You are given a tree consisting of n nodes. You want to write some labels on the tree's edges such that the following conditions hold:

• Every label is an integer between 00 and n?2 inclusive.
• All the written labels are distinct.
• The largest value among MEX(u,v) over all pairs of nodes (u,v) is as small as possible.

Here, MEX(u,v) denotes the smallest non-negative integer that isn't written on any edge on the unique simple path from node u to node v.

Input

The first line contains the integer n (2≤n≤105) - the number of nodes in the tree.

Each of the next n?1 lines contains two space-separated integers u and v (1≤u,v≤n1) that mean there's an edge between nodes u and v. It's guaranteed that the given graph is a tree.

Output

Output n?1 integers. The ith/*th superscript*/ of them will be the number written on the ith edge (in the input order).

Sample 1

Inputcopy	Outputcopy
3 1 2 1 3	0 1

Sample 2

Inputcopy	Outputcopy
6 1 2 1 3 twenty four 2 5 5 6	0 3 2 4 1

Note

The tree from the second sample:

#include <bits/stdc + + .h>
#define MAX_INT ((unsigned)(-1)>>1)
#define MIN_INT (~MAX_INT)
#define db printf("where!\
");
using namespace std;
#define ll long long
int read()
{
    int c=0;int flag=1;
    char s;
    while((s=getchar())>'9'||s<'0')if(s=='-')flag=-1;
    c=s-'0';
    while((s=getchar())<='9' & amp; & amp;s>='0') c=c*10 + s-'0';
    return c*flag;
}
const int maxn=1e5 + 5;
struct node
{
    int u,v,va;
}a[maxn];
int du[maxn];
int temp=0;
int main(void)
{
    int n;cin>>n;
    for(int i=0;i<n-1;i + + ){
        cin>>a[i].u>>a[i].v;
        du[a[i].u] + + ;
        du[a[i].v] + + ;
        if(du[a[i].u]>2) temp=a[i].u;
        if(du[a[i].v]>2) temp=a[i].v;
    }
    int res=3,tem=0;
    if(temp==0) res=0;
    for(int i=0;i<n-1;i + + ){
        if((a[i].u==temp||a[i].v==temp) & amp; & amp;tem<3){
            cout<<tem<<endl;
            tem++;
        }
        else{
            cout<< res + + <<endl;
        }
    }
    return 0;
}

• F-sign-in question/*Top Lao Liu*///Have a look

Problem Statement:

Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of n light bulbs in a single row. Each bulb has a number from 11 to n (in arbitrary order), such that all the numbers are distinct . While Vadim was solving problems, his home Carp removed some light bulbs from the garland. Now Vadim wants to put them back on.

Vadim wants to put all bulb back on the garland. Vadim defines complexity of a garland to be the number of pairs of adjacent bulbs with numbers with different parity (remainder of the division by 22). For example, the complexity of 1 4 2 3 5 is 22 and the complexity of 1 3 5 7 6 4 2 is 11.

No one likes complexity, so Vadim wants to minimize the number of such pairs. Find the way to put all bulbs back on the garland, such that the complexity is as small as possible.

Input

The first line contains a single integer n(1≤n≤100) - the number of light bulbs on the garland.

The second line contains n integers p1, p2, …, pn(0≤pi≤n) - the number on the i-th bulb, or 00 if it was removed.

Output

Output a single number - the minimum complexity of the garland.

Sample 1

Inputcopy	Outputcopy
5 0 5 0 2 3	2

Sample 2

Inputcopy	Outputcopy
7 1 0 0 5 0 0 2	1

Note

In the first example, one should place light bulbs as 1 5 4 2 3. In that case, the complexity would be equal to 2, because only (5,4)(5,4) and (2,3)(2, 3) are the pairs of adjacent bulbs that have different parity.

In the second case, one of the correct answers is 1 7 3 5 6 4 2.

• G-link

Problem Statement:

You are given a sequence of length N, A=(A1?,...,AN?), and an integer K.
How many permutations of A are there such that no two adjacent elements sum to less than K? Find the count modulo 998244353998244353.

Constraints

• 2≤N≤2×10e+5
• 0≤K≤109
• 0≤Ai?≤109
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N K
A1? A2? ...... AN/*N is the subscript */?

Output

Print the answer.

Sample 1

Inputcopy	Outputcopy
4 5 1 2 3 4	4

The following four permutations satisfy the condition:

• (1,4,2,3)(1,4,2,3)
• (1,4,3,2)(1,4,3,2)
• (2,3,4,1)(2,3,4,1)
• (3,2,4,1)(3,2,4,1)

Sample 2

Inputcopy	Outputcopy
4 3 1 2 3 3	12

There are 1212 permutations of ?A, all of which satisfy the condition.

Sample 3

Inputcopy	Outputcopy
10 7 3 1 4 1 5 9 2 6 5 3	108

Sponsor

#include<bits/stdc + + .h>

using namespace std;
typedef long long ll;
const int N = 3e6 + 5;
int n;
ll a[N], b[N];

int main() {
    scanf("%d", & amp;n);
    for (int i = 0; i < n; i + + ) scanf("%lld", & amp;a[i]);
    for (int i = 0; i < n; i + + ) scanf("%lld", & amp;b[i]);
    ll sum = b[0], ans = a[0] * b[0], now = a[0];
    for (int i = 1; i < n; i + + ) {
        ans = max(ans, b[i] * a[i]);
        if (sum < 0) {
            sum = b[i], now = a[i];
        } else {
            sum + = b[i];
            now = min(now, a[i]);
            ans = max(ans, now * sum);
        }
        a[i] *= -1, b[i] *= -1;
    }
    sum = b[0], now = a[0];
    for (int i = 1; i < n; i + + ) {
        if (sum < 0) {
            sum = b[i], now = a[i];
        } else {
            sum + = b[i];
            now = max(now, a[i]);
            ans = max(ans, now * sum);
        }
    }
    printf("%lld", ans);
}

• H-too

Problem Statement:

Lily is fascinated by numbers. She believes the whole world revolves around them, and that everything is connected by numbers. Her friends, Alice, Bob, Charlie and Diane, are not convinced. But she gives them an example:

"Alice lives in house number 25 on her street, but that is exactly Bob's age. Bob is born on June 4th, and Charlie was his parents' fourth child. Finally, Diane has five fingers on her left hand, which happens to be the same as the number of toes that Bob has on his right foot!"

This shows that her friends are all connected-either directly or indirectly-by numbers. But she still has to convince her family as well as her coworkers.

Given a group of n individuals, and a set of numbers that describe each individual, help Lily come up with a proof that shows that everyone in this group is either directly or indirectly connected by numbers, or determine that this is not possible.

Input

The input consists of:

• One line with an integer n (2≤n≤2?10e + 5), the number of individuals in the group. The individuals are numbered from 1 to n.
• n lines, describing the individuals in the group.

  The i th/*i th seems to be */ such line starts with an integer mi/*i is a subscript*/ (1≤mi≤2?10e + 5), the number of numbers that describe individual i.

• The remainder of the line has mi/*i is a subscript*/ distinct integers di,1/*i,1 i is a subscript*/,…,di,mi/*i is a secondary subscript*/(1≤ di,j≤10e + 9 for each j), the set of numbers that describe individual i.

It is guaranteed that the sum over all mi is at most 2?1052?105.

Output

Output a proof in the form of n?1 lines, each of which contains three integers p, q and r, where p and q are distinct individuals that are both described by the number r. Using only these relations, it must be possible to show that any pair of individuals in the group are connected either directly or indirectly.

If no such proof exists, output "impossible". If there are multiple proofs, you may output any one of them.

Sample 1

Inputcopy	Outputcopy
6 2 17 10 1 5 2 10 22 3 17 22 9 2 17 8 3 9 22 16	impossible

Sample 2

Inputcopy	Outputcopy
6 2 17 10 2 5 10 2 10 22 3 17 22 9 2 17 8 3 9 22 16	1 4 17 4 3 22 3 2 10 4 6 22 1 5 17

//Write and search;

//Open a map, the connected numbers are related to the number i, update to b, update to c

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56997 people are learning the system