QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#543649#18. Police Station5un_xiaomivita_msgCompile Error//C++141.5kb2024-09-01 17:46:052024-09-01 17:46:06

Judging History

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

  • [2024-09-01 17:46:06]
  • 评测
  • [2024-09-01 17:46:05]
  • 提交

answer

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;

#define G(x) ll x; cin >> x;
#define F(i, l, r) for(ll i = l; i < (r); ++i)
#define N 1000010

vl graph[N], rGraph[N], sccList[N], ord;
set<ll> sccGraph[N];
ll scc[N]; //sccs are 1-indexed
bool used[N];

void dfs1(ll i) {
    used[i] = true;
    for(ll j : graph[i]) if(!used[j]) dfs1(j);
    ord.push_back(i);
}

void dfs2(ll i, ll c) {
    scc[i] = c;
    sccList[c].push_back(i);
    for(ll j : rGraph[i]) if(!scc[j]) dfs2(j, c);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    G(n) G(m)
    while(m--) {
        G(u) G(v)
        graph[u].push_back(v);
        rGraph[v].push_back(u);
    }
    F(i, 1, n + 1) if(!used[i]) dfs1(i);
    ll c = 1;
    reverse(ord.begin(), ord.end());
    for(ll i : ord) if(!scc[i]) dfs2(i, c++);
    vector<ll> in(n+1);

    F(i, 1, n + 1) for(ll j : graph[i]) if(scc[j] - scc[i]) {
        sccGraph[scc[i]].insert(scc[j]);
        in[scc[j]]++;
    }

    ll ans = 0;
    F(i, 1, c) if (!in[i]) {
        if (!ans) ans = i;
        else {
            cout << "0\n"; exit(0);
        }
    }

    cout << sccList[ans].size() << '\n';
    sort(sccList[ans].begin(), sccList[ans].end());
    for (auto x: sccList[ans]) cout << x << " "; cout << endl;
    
}

Details

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/queue:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:157:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~