QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#871244 | #8622. London Underground | ucup-team6275# | AC ✓ | 797ms | 137344kb | C++23 | 4.4kb | 2025-01-25 20:01:10 | 2025-01-25 20:01:11 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("avx,avx,fma")
using namespace std;
using ll = long long;
using ld = long double;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for (int i = 0; i < (n); i += 1)
#define len(a) ((int)(a).size())
mt19937 rnd(234);
const ll inf = 1e18;
const ll mod = 998244353;
int n, m;
vector<string> stations;
vector<pair<string, string>> connections;
vector<vector<int>> g;
vector<string> mega_stations = {
"Baker_Street",
"Liverpool_Street",
};
vector<int> mega_nodes;
map<vector<int>, ll> mp;
ll get_with_split(vector<int> cur);
bool dfs(int v, vector<int> &cur, vector<int> &ncur, vector<int> &usd) {
usd[v] = true;
bool result = true;
for (auto to : g[v]) {
if (!cur[to]) {
continue;
}
if (ncur[to]) {
result = false;
}
if (usd[to]) {
continue;
}
if (!dfs(to, cur, ncur, usd)) {
result = false;
}
}
ncur[v] = true;
return result;
}
ll get(vector<int> cur) {
auto it = mp.find(cur);
if (it != mp.end()) {
return it->second;
}
ll &value = mp[cur];
int mx_deg = -1;
int opt = -1;
for (auto v : mega_nodes) {
if (cur[v]) {
opt = v;
break;
}
}
if (opt == -1) {
rep(v, n) {
if (!cur[v]) {
continue;
}
int mdeg = 0;
for (auto to : g[v]) {
if (cur[to]) {
mdeg += 1;
}
}
if (mdeg > mx_deg) {
mx_deg = mdeg;
opt = v;
}
}
}
if (opt == -1) {
return value = 1;
}
cur[opt] = 0;
ll result = get_with_split(cur);
for (auto to : g[opt]) {
cur[to] = false;
}
result = (result + get_with_split(cur)) % mod;
return value = result;
}
array<ll, 2> dfs_tree(int v, vector<int> &cur, vector<int> &usd) {
usd[v] = true;
array<ll, 2> res = {1, 1};
for (auto to : g[v]) {
if (usd[to] || !cur[to]) {
continue;
}
auto tors = dfs_tree(to, cur, usd);
res[1] = (res[1] * tors[0]) % mod;
res[0] = (res[0] * (tors[0] + tors[1])) % mod;
}
return res;
}
ll solve_tree(int v, vector<int> &cur) {
vector<int> usd(n, false);
auto res = dfs_tree(v, cur, usd);
return (res[0] + res[1]) % mod;
}
ll get_with_split(vector<int> cur) {
ll result = 1;
vector<int> usd(n, false);
for (int v = 0; v < n; v += 1) {
if (usd[v] or !cur[v]) {
continue;
}
vector<int> ncur(n, false);
if (dfs(v, cur, ncur, usd)) {
result = (result * solve_tree(v, ncur)) % mod;
} else {
result = (result * get(ncur)) % mod;
}
}
return result;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> m;
connections.resize(m);
for (auto &[a, b] : connections) {
cin >> a >> b;
stations.push_back(a);
stations.push_back(b);
}
sort(all(stations));
stations.resize(unique(all(stations)) - stations.begin());
n = len(stations);
g.assign(n, {});
for (auto [a, b] : connections) {
int u = lower_bound(all(stations), a) - stations.begin();
int v = lower_bound(all(stations), b) - stations.begin();
g[u].push_back(v);
g[v].push_back(u);
}
mega_nodes.clear();
for (auto a : mega_stations) {
int v = lower_bound(all(stations), a) - stations.begin();
assert(v < n and stations[v] == a);
mega_nodes.push_back(v);
}
vector<int> cur(n, true);
int k;
cin >> k;
bool ok = true;
rep(i, k) {
string a;
cin >> a;
int v = lower_bound(all(stations), a) - stations.begin();
if (!cur[v]) {
ok = false;
}
cur[v] = false;
for (auto to : g[v]) {
cur[to] = false;
}
}
if (!ok) {
cout << 0 << "\n";
return 0;
}
ll result = get_with_split(cur);
cout << result << "\n";
return 0;
}
/*
2
a b
b c
0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 64ms
memory: 15616kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
159589981
result:
ok 1 number(s): "159589981"
Test #2:
score: 0
Accepted
time: 83ms
memory: 17664kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
434129880
result:
ok 1 number(s): "434129880"
Test #3:
score: 0
Accepted
time: 797ms
memory: 137344kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
265208483
result:
ok 1 number(s): "265208483"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
538295197
result:
ok 1 number(s): "538295197"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 386ms
memory: 70144kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
336817147
result:
ok 1 number(s): "336817147"
Test #9:
score: 0
Accepted
time: 98ms
memory: 22272kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
400446333
result:
ok 1 number(s): "400446333"
Test #10:
score: 0
Accepted
time: 175ms
memory: 32512kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
976542866
result:
ok 1 number(s): "976542866"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
602812360
result:
ok 1 number(s): "602812360"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
8
result:
ok 1 number(s): "8"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
505 Baker_Street Regents_Park Charing_Cross Embankment Edgware_Road__Bakerloo_ Marylebone Embankment Waterloo Harlesden Willesden_Junction Harrow_and_Wealdstone Kenton Kensal_Green Queens_Park Kenton South_Kenton Kilburn_Park Maida_Vale Lambeth_North Elephant_and_Castle Maida_Vale Warwick_Avenue Mar...
output:
1
result:
ok 1 number(s): "1"
Extra Test:
score: 0
Extra Test Passed