oj.uz

답안 #521408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521408 2022-02-02T05:04:45 Z blue 어르신 집배원 (BOI14_postmen) C++17
100 / 100
 496 ms 82868 KB 
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

const int mx = 500'000;

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())


int N, M;

vi u(1+mx), v(1+mx);
vi edge[1+mx];

vi visit(1+mx, 0);

vi adj_ind(1+mx, 0);

vi instack(1+mx, 0);
vi st;

vvi res;


// int ct = 0;


void dfs(int x)
{
    // if(++ct == 50) exit(0);
    // cerr << "dfs " << x << '\n';
    while(adj_ind[x] < sz(edge[x]) && visit[ edge[x][adj_ind[x]] ])
    {
        adj_ind[x]++;
        // cerr << adj_ind[x] << '\n';
    }

    if(adj_ind[x] == sz(edge[x])) return;

    int e = edge[x][adj_ind[x]];
    // cerr << "edge = " << e << '\n';

    int y = u[e] + v[e] - x;

    visit[e] = 1;
    // cerr << "visit : " << e << '\n';

    if(instack[y])
    {
        res.push_back(vi(0));
        while(1)
        {
            // cerr << "w\n";
            res.back().push_back(st.back());
            if(st.back() == y) break;
            instack[st.back()] = 0;
            st.pop_back();
        }
        // cerr << x << " -> " << y << '\n';
        dfs(y);
        // cerr << "done instack\n";
    }
    else
    {
        instack[y] = 1;
        st.push_back(y);
        dfs(y);
    }

    // cerr << "terminate dfs\n";

}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    for(int e = 1; e <= M; e++)
    {
        cin >> u[e] >> v[e];
        edge[u[e]].push_back(e);
        edge[v[e]].push_back(e);
    }

    for(int e = 1; e <= M; e++)
    {
        while(!visit[e])
        {
            // cerr << "e = " << e << '\n';
            st.push_back(u[e]);
            instack[u[e]] = 1;
            dfs(u[e]);
            // cerr << "###\n";
            // cerr << visit[e] << '\n';
            instack[u[e]] = 0;
            // cerr << "instack cleared\n";
            // exit(0);
            // st.clear();
            // cerr << "st cleared\n";
            // cerr << "while instance done\n";
        }
        // cerr << "e = " << e << " done \n";
    }

    for(vi& r: res) 
    {
        for(int u: r) 
            cout << u << ' ';
        cout << '\n';
    }
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 21836 KB Output is correct
2 Correct 12 ms 21872 KB Output is correct
3 Correct 11 ms 21836 KB Output is correct
4 Correct 13 ms 22136 KB Output is correct
5 Correct 15 ms 21860 KB Output is correct
6 Correct 13 ms 22220 KB Output is correct
7 Correct 17 ms 23176 KB Output is correct
8 Correct 12 ms 22084 KB Output is correct
9 Correct 42 ms 30832 KB Output is correct
10 Correct 12 ms 21964 KB Output is correct
11 Correct 12 ms 22140 KB Output is correct
12 Correct 49 ms 31160 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21836 KB Output is correct
2 Correct 11 ms 21836 KB Output is correct
3 Correct 13 ms 21868 KB Output is correct
4 Correct 14 ms 22120 KB Output is correct
5 Correct 12 ms 21872 KB Output is correct
6 Correct 13 ms 22264 KB Output is correct
7 Correct 22 ms 23220 KB Output is correct
8 Correct 12 ms 22008 KB Output is correct
9 Correct 42 ms 30812 KB Output is correct
10 Correct 15 ms 22064 KB Output is correct
11 Correct 12 ms 22092 KB Output is correct
12 Correct 53 ms 31124 KB Output is correct
13 Correct 69 ms 33856 KB Output is correct
14 Correct 65 ms 27432 KB Output is correct
15 Correct 70 ms 32116 KB Output is correct
16 Correct 71 ms 33816 KB Output is correct
17 Correct 70 ms 28272 KB Output is correct
18 Correct 70 ms 32152 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 21836 KB Output is correct
2 Correct 12 ms 21848 KB Output is correct
3 Correct 11 ms 21820 KB Output is correct
4 Correct 13 ms 22208 KB Output is correct
5 Correct 12 ms 21872 KB Output is correct
6 Correct 13 ms 22176 KB Output is correct
7 Correct 15 ms 23276 KB Output is correct
8 Correct 12 ms 22044 KB Output is correct
9 Correct 47 ms 30876 KB Output is correct
10 Correct 12 ms 22148 KB Output is correct
11 Correct 13 ms 22096 KB Output is correct
12 Correct 51 ms 31096 KB Output is correct
13 Correct 83 ms 33780 KB Output is correct
14 Correct 60 ms 27332 KB Output is correct
15 Correct 71 ms 32040 KB Output is correct
16 Correct 64 ms 33856 KB Output is correct
17 Correct 87 ms 28208 KB Output is correct
18 Correct 64 ms 32148 KB Output is correct
19 Correct 451 ms 82868 KB Output is correct
20 Correct 416 ms 50608 KB Output is correct
21 Correct 371 ms 72756 KB Output is correct
22 Correct 427 ms 82856 KB Output is correct
23 Correct 183 ms 66196 KB Output is correct
24 Correct 496 ms 54036 KB Output is correct
25 Correct 461 ms 74764 KB Output is correct