QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414524#18. Police Stationx-camp0 11ms78844kbC++172.7kb2024-05-19 07:08:562024-05-19 07:08:56

Judging History

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

  • [2024-05-19 07:08:56]
  • 评测
  • 测评结果:0
  • 用时:11ms
  • 内存:78844kb
  • [2024-05-19 07:08:56]
  • 提交

answer

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#define MX 1000002
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];
set<int> sccadj[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);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v])
            low[u] = min(low[u], disc[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) {
    if (visited[u]) return;
    visited[u] = true;
    rcnt[u] ++ ;
    for (auto v: sccadj[u]) {
        if (!visited[v])
            dfs(v);
        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);
    }
    for (int i = 1; i <= N; ++i) {
        for (auto x: adj[i])
            if (sid[i] != sid[x])
                sccadj[sid[i]].insert(sid[x]);
    }
    set<int> nodes;
    for (int i=0; i<scnt; i++) {
        if (!visited[i]) {
            dfs(i);
            if (rcnt[i] == scnt) {
                for (auto x: SCCs[i])
                    nodes.insert(x);
                break;
            }
        }
    }
    
    if (nodes.empty())
        cout << 0 << endl;
    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: 4ms
memory: 78676kb

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: 4ms
memory: 78844kb

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: 11ms
memory: 76792kb

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: 11ms
memory: 78612kb

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%