oj.uz

답안 #683058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683058 2023-01-17T15:29:41 Z Vladth11 어르신 집배원 (BOI14_postmen) C++14
100 / 100
 453 ms 71044 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef pair <int, int> pii;
typedef long long ll;

const int NMAX = 500001;
const int VMAX = 41;
const int INF = 1e9;
const int MOD = 1000000009;
const int BLOCK = 318;
const int base = 31;
const int nrbits = 21;

struct muchie {
    int ambele;
    int viz;
} edges[NMAX];

vector <int> v[NMAX];

vector <int> euler;

void DFS(int node) {
    while(v[node].size()) {
        int ind = v[node].back();
        v[node].pop_back();
        if(edges[ind].viz == 1) continue;
        edges[ind].viz = 1;
        int vecin = (edges[ind].ambele ^ node);
        DFS(vecin);
    }
    euler.push_back(node);
}

vector <int> stiva;
int f[NMAX];

int main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, i;
    cin >> n >> m;
    for(i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        edges[i].ambele = (x ^ y);
        edges[i].viz = 0;
        v[x].push_back(i);
        v[y].push_back(i);
    }
    DFS(1);
    for(auto x : euler) {
        if(f[x]) {
            while(stiva.back() != x) {
                cout << stiva.back() << " ";
                f[stiva.back()]--;
                stiva.pop_back();
            }
            cout << stiva.back() << " ";
            f[stiva.back()]--;
            stiva.pop_back();
            cout << "\n";
        }
        stiva.push_back(x);
        f[x]++;
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 8 ms 11988 KB Output is correct
4 Correct 11 ms 12248 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 7 ms 12372 KB Output is correct
7 Correct 10 ms 13268 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 39 ms 19460 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 11 ms 12196 KB Output is correct
12 Correct 42 ms 19652 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 12084 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 9 ms 12348 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 17 ms 12460 KB Output is correct
7 Correct 11 ms 13248 KB Output is correct
8 Correct 7 ms 12208 KB Output is correct
9 Correct 38 ms 19520 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 9 ms 12244 KB Output is correct
12 Correct 53 ms 20432 KB Output is correct
13 Correct 66 ms 23692 KB Output is correct
14 Correct 72 ms 20464 KB Output is correct
15 Correct 51 ms 21956 KB Output is correct
16 Correct 64 ms 23608 KB Output is correct
17 Correct 67 ms 17984 KB Output is correct
18 Correct 52 ms 21308 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 11 ms 12336 KB Output is correct
5 Correct 8 ms 12188 KB Output is correct
6 Correct 8 ms 12364 KB Output is correct
7 Correct 11 ms 13268 KB Output is correct
8 Correct 7 ms 12232 KB Output is correct
9 Correct 39 ms 19556 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 9 ms 12364 KB Output is correct
12 Correct 39 ms 20516 KB Output is correct
13 Correct 61 ms 23628 KB Output is correct
14 Correct 54 ms 20492 KB Output is correct
15 Correct 55 ms 22112 KB Output is correct
16 Correct 56 ms 23624 KB Output is correct
17 Correct 68 ms 18004 KB Output is correct
18 Correct 52 ms 21380 KB Output is correct
19 Correct 440 ms 71036 KB Output is correct
20 Correct 370 ms 55044 KB Output is correct
21 Correct 406 ms 62284 KB Output is correct
22 Correct 402 ms 71044 KB Output is correct
23 Correct 161 ms 51716 KB Output is correct
24 Correct 453 ms 42584 KB Output is correct
25 Correct 391 ms 59500 KB Output is correct