QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414508 | #18. Police Station | x-camp | 0 | 5ms | 31052kb | C++17 | 2.6kb | 2024-05-19 05:44:19 | 2024-05-19 05:44:20 |
Judging History
answer
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#define MX 1000001
using namespace std;
int N,M; // Number of vertices
vector<int> adj[MX]; // Adjacency list
vector<int> disc; // Discovery time of each vertex
vector<int> low; // Lowest discovery time reachable from the vertex
stack<int> st; // Stack to store the vertices of the current SCC
vector<bool> inStack; // Boolean array to check if a vertex is in the stack
int cnt; // Time counter
vector<vector<int>> SCCs; // List of all SCCs
int sid[MX]; // scc id
int rcnt[MX]; // reach count from each node
int scnt; //scc count
bool visited[MX];
void scc(int u) {
// Initialize discovery time and low value
disc[u] = low[u] = ++cnt;
st.push(u);
inStack[u] = true;
// Go through all vertices adjacent to this
for (int v : adj[u]) {
if (disc[v] == -1)
scc(v);
if (inStack[v])
low[u] = min(low[u], low[v]);
}
if (low[u] == disc[u]) { //found SCC
vector<int> scc;
for (int v=st.top();; v=st.top()) {
st.pop();
inStack[v] = false;
scc.push_back(v);
if (v == u) break;
}
SCCs.push_back(scc);
for (auto x: scc)
sid[x] = scnt;
scnt ++;
}
}
void dfs(int u, set<int> sccadj[]) {
if (visited[u]) return;
visited[u] = true;
rcnt[u] ++ ;
for (auto v: sccadj[u]) {
if (!visited[sid[v]])
dfs(v, sccadj);
rcnt[u] += rcnt[v];
}
}
int main() {
cin >> N >> M;
disc.assign(N+1, -1);
low.assign(N+1, -1);
inStack.assign(N+1, false);
for (int i=0; i<M; i++) {
int a,b;
cin >> a >> b;
adj[a].push_back(b);
}
for (int i = 1; i <= N; ++i) {
if (disc[i] == -1)
scc(i);
}
set<int> nodes;
set<int> sccadj[scnt];
for (int i = 1; i <= N; ++i) {
for (auto x: adj[i])
if (sid[i] != sid[x])
sccadj[sid[i]].insert(sid[x]);
}
for (int i=0; i<scnt; i++) {
if (!visited[i]) {
dfs(i , sccadj);
if (rcnt[i] == scnt)
for (auto x: SCCs[i])
nodes.insert(x);
}
}
if (nodes.empty())
cout << 0;
else {
cout << nodes.size() << endl;
for (auto x: nodes)
cout << x << " ";
cout << endl;
}
/*for (auto &s: SCCs) {
for (auto v: s)
cout << v << " " ;
cout << endl;
}*/
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 0ms
memory: 29420kb
input:
951 1923 800 351 371 252 858 700 139 519 10 778 73 554 273 867 745 917 936 933 697 707 825 881 847 732 90 905 720 86 231 352 255 374 943 80 720 81 868 365 595 545 226 655 28 192 50 876 752 852 485 294 814 700 870 491 153 438 111 699 813 673 296 40 426 463 270 168 417 523 391 192 693 344 251 7 660 78...
output:
0
result:
ok single line: '0'
Test #2:
score: 30
Accepted
time: 5ms
memory: 31052kb
input:
602 1232 494 366 52 346 307 279 410 457 268 296 79 407 421 169 90 106 581 187 103 16 3 12 386 312 100 310 48 367 481 168 594 411 476 122 132 122 533 578 430 146 487 397 328 23 233 50 597 443 362 176 239 328 348 96 284 523 297 349 355 9 373 359 96 166 195 261 457 62 3 251 53 56 484 309 332 22 547 295...
output:
0
result:
ok single line: '0'
Test #3:
score: 30
Accepted
time: 4ms
memory: 29388kb
input:
586 1520 204 256 220 515 265 404 154 217 127 488 310 462 486 523 55 269 402 166 471 414 421 585 339 275 19 499 319 487 19 520 32 398 456 269 445 232 248 402 263 520 507 353 382 453 284 225 248 461 321 504 230 30 114 293 169 333 141 385 4 550 490 482 419 155 545 500 342 539 293 544 582 392 4 92 136 4...
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 29704kb
input:
742 2763 257 56 377 732 470 258 479 465 114 138 199 368 82 49 254 264 165 641 712 568 230 543 632 88 465 241 106 223 624 179 702 567 211 142 51 77 329 232 9 333 192 324 708 602 436 579 636 277 659 509 53 391 704 225 123 681 109 515 203 517 554 505 326 102 691 46 155 692 606 22 497 710 375 353 244 68...
output:
0
result:
wrong answer 1st lines differ - expected: '716', found: '0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%