oj.uz

답안 #880005

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880005 2023-11-28T14:46:22 Z Karoot 어르신 집배원 (BOI14_postmen) C++17
100 / 100
 331 ms 99648 KB 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
 
#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()
 
using namespace std;
 
typedef long long ll;
 
ll linf = 1e15+1;
 
inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
const int MAXN = 5e5+1;
bool edgeVisited[MAXN];
vector<pair<int, int>> adj[MAXN];
bool isVisited[MAXN];
int startNode;
int neighIndex[MAXN];
 
vector<vector<int> > sols;
vector<int> temp;
 
int counter = 0;
//Destination, ID
 
bool dfs(int node, int usedEdge){
    edgeVisited[usedEdge] = true;
    if (isVisited[node]){
        startNode = node;
        return true;
    }
 
    //counter++;
 
    isVisited[node] = true;
    //cout << node << ": " << usedEdge << endl;
    while (neighIndex[node] < adj[node].size()){
        pair<int, int> e = adj[node][neighIndex[node]++];
        if (!edgeVisited[e.second]){
            bool ret = dfs(e.first, e.second);
            if (ret){
                temp.push_back(node);
                //hasEdges[node] -= 2;
                if (node == startNode){
                    sols.push_back(temp);
                    temp.clear();
                } else {
                    isVisited[node] = false;
                    return true;
                }
            }
        } else {
            counter++;
        }
    }
 
    isVisited[node] = false;
    return false;
}
 
int main(){
    scoobydoobydoo();
    //freopen("seniorPostmen.in", "r", stdin);
    //freopen("seniorPostmen.ans", "w", stdout);
    int n, m; cin >> n >> m;
 
    for (int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back({b, i+1});
        adj[b].push_back({a, i+1});
    }
 
    //cout << maxi << endl
 
 
    
    for (int i = 1; i <= n; i++){
        if (!isVisited[i])dfs(i, 0);
    }
 
    //cout << counter << "\n";
 
    for (auto& v : sols){
        for (auto& e : v){
            cout << e << " ";
        }
        cout << "\n";
    }
    
 
 
 
    return 0;
}

Compilation message

postmen.cpp: In function 'bool dfs(int, int)':
postmen.cpp:51:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while (neighIndex[node] < adj[node].size()){
      |            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 7 ms 13404 KB Output is correct
8 Correct 4 ms 13148 KB Output is correct
9 Correct 23 ms 16212 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 25 ms 16720 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 8 ms 13404 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 23 ms 16116 KB Output is correct
10 Correct 4 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 26 ms 16732 KB Output is correct
13 Correct 42 ms 29900 KB Output is correct
14 Correct 35 ms 18892 KB Output is correct
15 Correct 33 ms 19144 KB Output is correct
16 Correct 43 ms 29900 KB Output is correct
17 Correct 38 ms 19348 KB Output is correct
18 Correct 38 ms 21712 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12788 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12776 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 7 ms 13468 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 24 ms 16212 KB Output is correct
10 Correct 4 ms 13144 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 26 ms 16732 KB Output is correct
13 Correct 44 ms 29900 KB Output is correct
14 Correct 36 ms 18892 KB Output is correct
15 Correct 43 ms 19144 KB Output is correct
16 Correct 42 ms 29900 KB Output is correct
17 Correct 45 ms 19476 KB Output is correct
18 Correct 38 ms 21712 KB Output is correct
19 Correct 331 ms 99648 KB Output is correct
20 Correct 297 ms 45208 KB Output is correct
21 Correct 230 ms 46768 KB Output is correct
22 Correct 328 ms 99508 KB Output is correct
23 Correct 117 ms 29184 KB Output is correct
24 Correct 281 ms 48148 KB Output is correct
25 Correct 274 ms 59980 KB Output is correct