Description

Niflheimr is playing Minecraft recently. He occupies a lot of towns, and there are many diamonds inside some of those towns.

Whenever he runs out of diamond, he has to figure out the nearest town with diamonds from his current location.

Doing this task every time waste a lot of time. He asks you to help him for the calculation. For every town, find the shortest distance to get diamonds from a nearby town which has diamonds. If the town itself has diamonds, the distance would be 0.

Hint: Use BFS (Breadth First Search) and std::queue.

If you are not familiar with BFS, you should take a look at the following article:

http://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html

[IMPORTANT] For those almost run out of time, maybe this note can help you figure out BFS and solve this problem faster!

You are provided with the following code:

#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// G[i] is the neighbor towns of town i
vector<int> diamondTowns;
vector<int> G[100005];
int Dist[100005];

struct node {
    int id;
    int dist;
    node(int id, int l) {
        this->id = id;
        this->dist = l;
    }
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        diamondTowns.push_back(x);
    }
    fill(Dist, Dist+100005, -1);

    queue<node> Q;

    // [TODO] complete the task!

    // Output
    for (int i = 1; i <= N; i++) {
        cout << Dist[i] << '\n';
    }
    return 0;
}

 You may take it as reference. You are not required to use this code, though.

Input

First line of input contains three integer N, M, K, denoting the number of towns, the amount of roads between towns and the number of towns which has diamond.

All the towns are numbered from 1 to N.

For the next M lines, each of them contains two integer a, b, meaning there is a road between a and b. All the roads are bidirectional, and the length of these roads are all 1.

The last line of input contains K distinct integers, denoting the towns which has diamonds.

It is guaranteed that:

• 1 <= K <= N <= 10⁵
• 1 <= M <= min(10⁶, N*(N+1)/2)
• All the towns can reach each other, i.e. the graph is connected.

Output

Output consists of N lines.

For i-th line, output the shortest distance Niflheimr has to travel from town i to get a diamond.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Several men and women are going to attend the singles mixer (聯誼會) tonight. As the organizer, you have collected the personal score of each participant. Several independent events will occur during the party. Each event has a random lucky value e_i. If the sum of the scores of a man and a woman equals e_i, they will form a perfect pair and dance together. However, since this is a singles mixer and the events are independent, a specific man/woman may dance with a different woman/man in a different event.

Your staff has shown you the lucky value of each event. To gain more control over the party, you want to calculate whether there is a perfect pair in each event before the singles mixer.

!!WARNING!!

You may get TLE if you use std::set and the compile language C++ is chosen, instead of C++11.

Input

The first line contains 3 positive integers M, W and E, where there're M men, W women and E events.

The second line contains M integers, denoting the personal score of each man.

The third line contains W integers, denoting the personal score of each woman.

Next, followed by E lines, each line has the lucky score e_i.

Constraints:

• Cases 1~2 : either the score of every man or woman is 0
  E=200000; M+W<200000
• Cases 3~4 : either the score of every man or woman is the same (e.g. all of the men have the score of 87)
  E=200000; M+W<200000
• Cases 5~8: M+W<200000; min(M, W)*log₂(max(M, W))*E < 10⁸;

The absolute values of all scores range in [0, 10⁷).

Output

For each event, if there exist at least a perfect pair, print "Yes"  in a line; otherwise, print "No". Remember to add a '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss