QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#871244#8622. London Undergrounducup-team6275#AC ✓797ms137344kbC++234.4kb2025-01-25 20:01:102025-01-25 20:01:11

Judging History

你现在查看的是最新测评结果

  • [2025-01-25 20:01:11]
  • 评测
  • 测评结果:AC
  • 用时:797ms
  • 内存:137344kb
  • [2025-01-25 20:01:10]
  • 提交

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