2480 | 2023. 01. 13 12:06:21 | renn | Tom és Jerry2 (60) | cpp11 | Hibás válasz 0/60 | 532ms | 10940 KiB |
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
typedef vector<vector<int>> graf;
typedef vector<int> vi;
typedef vector<bool> vb;
inline int bfs(graf &g, int &k, vi &tavok)
{
queue<int> next;
next.push(k);
tavok[k] = 0;
int i;
while(!next.empty())
{
i = next.front();
next.pop();
for(auto &x : g[i])
{
if(tavok[x] > -1) continue;
next.push(x);
tavok[x] = tavok[i]+1;
}
}
return 0;
}
int timer;
void jerry_dfs(int v, int p, graf &adj, vb &volt, queue<int> &cuts, vi &tin, vi &low, vi &dist) {
volt[v] = true;
tin[v] = low[v] = timer++;
int children=0;
for (int to : adj[v]) {
if (to == p) continue;
if (volt[to]) {
low[v] = min(low[v], tin[to]);
} else {
jerry_dfs(to, v, adj, volt, cuts, tin, low, dist);
low[v] = min(low[v], low[to]);
if (low[to] >= tin[v] && p!=-1 && adj[v].size() > 1)
cuts.push(v);
++children;
}
}
if(p == -1 && children > 1 && adj[v].size() > 1)
cuts.push(v);
}
int main()
{
InTheNameOfGod
int n, m, t, jdb, j, e;
cin >> n >> m >> t >> jdb >> e;
e--;
t--;
vi tomd(n, -1);
graf tom(n);
graf jerry(n);
int a, b, c, d;
bool h;
while(m--)
{
cin >> a >> b >> c;
a--; b--;
if(((c&1)^1) && a!=e && b!=e)
{
tom[a].push_back(b);
tom[b].push_back(a);
}
jerry[a].push_back(b);
jerry[b].push_back(a);
}
bfs(tom, t, tomd);
while(jdb--)
{
timer = 0;
vi jerryd(n, -1);
vb volt(n, false);
vi tin(n, -1);
vi low(n, -1);
cin >> j;
j--;
queue<int> cuts;
bfs(jerry, j, jerryd);
jerry_dfs(j, -1, jerry, volt, cuts, tin, low, jerryd);
h = false;
for(auto &x : jerryd)
cout << x << " ";
cout << "\n";
while(!cuts.empty())
{
d = cuts.front(); cuts.pop();
if(jerryd[d] > tomd[d])
{
cout << d+1 << "\n";
h = true;
break;
}
}
if(!h) cout << "0\n";
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 0/60 | ||||||
1 | Hibás válasz | 0/0 | 3ms | 1852 KiB | |||
2 | Időlimit túllépés | 0/0 | 456ms | 2784 KiB | |||
3 | Hibás válasz | 0/2 | 2ms | 1972 KiB | |||
4 | Hibás válasz | 0/2 | 2ms | 2088 KiB | |||
5 | Hibás válasz | 0/2 | 2ms | 2288 KiB | |||
6 | Hibás válasz | 0/3 | 3ms | 2376 KiB | |||
7 | Hibás válasz | 0/2 | 4ms | 2648 KiB | |||
8 | Hibás válasz | 0/2 | 48ms | 2716 KiB | |||
9 | Hibás válasz | 0/2 | 21ms | 2780 KiB | |||
10 | Hibás válasz | 0/3 | 72ms | 2912 KiB | |||
11 | Hibás válasz | 0/3 | 85ms | 3276 KiB | |||
12 | Hibás válasz | 0/3 | 333ms | 3792 KiB | |||
13 | Időlimit túllépés | 0/3 | 460ms | 3140 KiB | |||
14 | Időlimit túllépés | 0/3 | 474ms | 3600 KiB | |||
15 | Időlimit túllépés | 0/3 | 465ms | 3980 KiB | |||
16 | Időlimit túllépés | 0/3 | 469ms | 4220 KiB | |||
17 | Időlimit túllépés | 0/3 | 532ms | 5616 KiB | |||
18 | Időlimit túllépés | 0/3 | 460ms | 8116 KiB | |||
19 | Időlimit túllépés | 0/4 | 472ms | 7340 KiB | |||
20 | Időlimit túllépés | 0/4 | 469ms | 9648 KiB | |||
21 | Időlimit túllépés | 0/5 | 446ms | 9480 KiB | |||
22 | Időlimit túllépés | 0/5 | 521ms | 10940 KiB |