oj.uz

답안 #97100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97100 2019-02-13T20:50:30 Z dalgerok 어르신 집배원 (BOI14_postmen) C++14
100 / 100
 455 ms 55376 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 5e5 + 5;


int n, m, x[N], y[N], a[3 * N], sz;
vector < int > g[N];
bool used[N];
vector < int > q;


void dfs(int v){
    while(!g[v].empty()){
        int num = g[v].back();
        g[v].pop_back();
        if(used[num]){
            continue;
        }
        used[num] = true;
        int to = (x[num] ^ v ^ y[num]);
        dfs(to);
    }
    a[++sz] = v;
}

inline void read(int &x){
    x = 0;
    char c = getchar_unlocked();
    while(c < '0' || c > '9'){
        c = getchar_unlocked();
    }
    while('0' <= c && c <= '9'){
        x = x * 10 + c - '0';
        c = getchar_unlocked();
    }
}
inline void print(int x){
    int len = 0;
    while(x % 10 == 0){
        len += 1;
        x /= 10;
    }
    int y = 0;
    while(x){
        y = y * 10 + x % 10;
        x /= 10;
    }
    while(y){
        putchar_unlocked('0' + y % 10);
        y /= 10;
    }
    while(len--){
        putchar_unlocked('0');
    }
}

int main(){
    read(n);
    read(m);
    for(int i = 1; i <= m; i++){
        read(x[i]);
        read(y[i]);
        g[x[i]].push_back(i);
        g[y[i]].push_back(i);
    }
    dfs(1);
    memset(used, 0, sizeof(used));
    vector < int > s;
    for(int i = 1; i <= sz; i++){
        int it = a[i];
        if(!used[it]){
            used[it] = true;
            s.push_back(it);
        }
        else{
            while(s.back() != it){
                print(s.back());
                putchar_unlocked(' ');
                used[s.back()] = false;
                s.pop_back();
            }
            print(it);
            putchar_unlocked('\n');
        }
    }
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12544 KB Output is correct
2 Correct 11 ms 12544 KB Output is correct
3 Correct 13 ms 12544 KB Output is correct
4 Correct 13 ms 12800 KB Output is correct
5 Correct 12 ms 12672 KB Output is correct
6 Correct 12 ms 12800 KB Output is correct
7 Correct 16 ms 13564 KB Output is correct
8 Correct 13 ms 12800 KB Output is correct
9 Correct 27 ms 18304 KB Output is correct
10 Correct 17 ms 12672 KB Output is correct
11 Correct 13 ms 12808 KB Output is correct
12 Correct 29 ms 18432 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12544 KB Output is correct
2 Correct 14 ms 12544 KB Output is correct
3 Correct 11 ms 12628 KB Output is correct
4 Correct 11 ms 12800 KB Output is correct
5 Correct 17 ms 12672 KB Output is correct
6 Correct 13 ms 12800 KB Output is correct
7 Correct 14 ms 13568 KB Output is correct
8 Correct 14 ms 12672 KB Output is correct
9 Correct 29 ms 18168 KB Output is correct
10 Correct 14 ms 12800 KB Output is correct
11 Correct 12 ms 12800 KB Output is correct
12 Correct 34 ms 18400 KB Output is correct
13 Correct 71 ms 21152 KB Output is correct
14 Correct 50 ms 18608 KB Output is correct
15 Correct 56 ms 19648 KB Output is correct
16 Correct 62 ms 21108 KB Output is correct
17 Correct 63 ms 16856 KB Output is correct
18 Correct 61 ms 19268 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12536 KB Output is correct
2 Correct 12 ms 12544 KB Output is correct
3 Correct 13 ms 12544 KB Output is correct
4 Correct 12 ms 12928 KB Output is correct
5 Correct 22 ms 12672 KB Output is correct
6 Correct 24 ms 12800 KB Output is correct
7 Correct 15 ms 13440 KB Output is correct
8 Correct 18 ms 12800 KB Output is correct
9 Correct 31 ms 18272 KB Output is correct
10 Correct 13 ms 12800 KB Output is correct
11 Correct 12 ms 12672 KB Output is correct
12 Correct 32 ms 18432 KB Output is correct
13 Correct 72 ms 21108 KB Output is correct
14 Correct 57 ms 18524 KB Output is correct
15 Correct 55 ms 19696 KB Output is correct
16 Correct 57 ms 21156 KB Output is correct
17 Correct 75 ms 16888 KB Output is correct
18 Correct 61 ms 19192 KB Output is correct
19 Correct 447 ms 55268 KB Output is correct
20 Correct 376 ms 42480 KB Output is correct
21 Correct 360 ms 48332 KB Output is correct
22 Correct 455 ms 55376 KB Output is correct
23 Correct 101 ms 40312 KB Output is correct
24 Correct 441 ms 34436 KB Output is correct
25 Correct 426 ms 45804 KB Output is correct