1123 | 2022. 03. 04 10:22:26 | kideso | Sportos nyaralás | cpp14 | Hibás válasz 2/40 | 107ms | 29440 KiB |
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int n = 50000;
vector<int> p[n + 1], z[n + 1];
int pk[n + 1], zk[n + 1], ans[n + 1];
bool lp[n + 1], lz[n + 1];
int N, P, Z;
void szelp(int kp, int s) {
queue<int> y;
lp[kp] = true;
pk[kp] = s;
y.push(kp);
while (!y.empty()) {
int csp = y.front();
y.pop();
for (auto e : p[csp])
if (!lp[e]) {
lp[e] = true;
pk[e] = s;
y.push(e);
}
}
}
void szelz(int kp, int s) {
queue<int> y;
lz[kp] = true;
zk[kp] = s;
y.push(kp);
while (!y.empty()) {
int csp = y.front();
y.pop();
for (auto e : z[csp]) {
if (!lz[e]) {
lz[e] = true;
zk[e] = s;
y.push(e);
}
if (pk[e] * pk[csp] != 0){
if (pk[e] == pk[csp]) ++ans[csp];
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N >> P >> Z;
for (int i = 1; i <= P; ++i) {
int a, b;
cin >> a >> b;
p[a].push_back(b), p[b].push_back(a);
}
for (int i = 1; i <= Z; ++i) {
int a, b;
cin >> a >> b;
z[a].push_back(b), z[b].push_back(a);
}
int ps = 1, zs = 1;
for (int i = 1; i <= N; ++i) {
if (!lp[i]) {
szelp(i, ps);
++ps;
}
}
for (int i = 1; i <= N; ++i) {
if (!lz[i]) {
szelz(i, zs);
++zs;
}
}
for (int i = 1; i <= N; ++i)
cout << ans[i] << ' ';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 2/40 | ||||||
1 | Elfogadva | 0/0 | 4ms | 6532 KiB | |||
2 | Hibás válasz | 0/0 | 71ms | 15708 KiB | |||
3 | Elfogadva | 1/1 | 4ms | 7936 KiB | |||
4 | Hibás válasz | 0/1 | 4ms | 7936 KiB | |||
5 | Hibás válasz | 0/1 | 4ms | 7940 KiB | |||
6 | Elfogadva | 1/1 | 3ms | 7948 KiB | |||
7 | Hibás válasz | 0/1 | 3ms | 7952 KiB | |||
8 | Hibás válasz | 0/1 | 3ms | 7956 KiB | |||
9 | Hibás válasz | 0/1 | 4ms | 7960 KiB | |||
10 | Hibás válasz | 0/1 | 4ms | 8168 KiB | |||
11 | Hibás válasz | 0/2 | 4ms | 8212 KiB | |||
12 | Hibás válasz | 0/2 | 4ms | 8240 KiB | |||
13 | Hibás válasz | 0/2 | 8ms | 9072 KiB | |||
14 | Hibás válasz | 0/2 | 8ms | 9104 KiB | |||
15 | Hibás válasz | 0/2 | 27ms | 12468 KiB | |||
16 | Hibás válasz | 0/2 | 37ms | 14348 KiB | |||
17 | Hibás válasz | 0/3 | 43ms | 16116 KiB | |||
18 | Hibás válasz | 0/3 | 46ms | 17084 KiB | |||
19 | Hibás válasz | 0/2 | 50ms | 16848 KiB | |||
20 | Hibás válasz | 0/2 | 54ms | 20300 KiB | |||
21 | Hibás válasz | 0/2 | 64ms | 22152 KiB | |||
22 | Hibás válasz | 0/2 | 56ms | 22632 KiB | |||
23 | Hibás válasz | 0/3 | 107ms | 26348 KiB | |||
24 | Hibás válasz | 0/3 | 104ms | 29440 KiB |