oj.uz

답안 #683057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683057 2023-01-17T15:29:10 Z Vladth11 어르신 집배원 (BOI14_postmen) C++14
38 / 100
 500 ms 21276 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) {
        debug(x);
        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 7 ms 12088 KB Output is correct
4 Correct 22 ms 12396 KB Output is correct
5 Correct 12 ms 12064 KB Output is correct
6 Correct 31 ms 12472 KB Output is correct
7 Correct 96 ms 13516 KB Output is correct
8 Correct 16 ms 12224 KB Output is correct
9 Correct 476 ms 20752 KB Output is correct
10 Correct 23 ms 12440 KB Output is correct
11 Correct 21 ms 12340 KB Output is correct
12 Correct 485 ms 21276 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12084 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 11992 KB Output is correct
4 Correct 21 ms 12404 KB Output is correct
5 Correct 12 ms 12116 KB Output is correct
6 Correct 28 ms 12500 KB Output is correct
7 Correct 89 ms 13404 KB Output is correct
8 Correct 18 ms 12244 KB Output is correct
9 Execution timed out 519 ms 20732 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12080 KB Output is correct
2 Correct 7 ms 12008 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 24 ms 12396 KB Output is correct
5 Correct 13 ms 12084 KB Output is correct
6 Correct 29 ms 12500 KB Output is correct
7 Correct 79 ms 13452 KB Output is correct
8 Correct 16 ms 12288 KB Output is correct
9 Execution timed out 510 ms 20716 KB Time limit exceeded
10 Halted 0 ms 0 KB -