oj.uz

답안 #902387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
902387 2024-01-10T11:01:50 Z damamila 어르신 집배원 (BOI14_postmen) C++14
0 / 100
 3 ms 904 KB 
#include <bits/stdc++.h>
   
using namespace std;

#define int long long

vector<vector<pair<int, int>>> g;
vector<bool> seen;
vector<int> seq;

void dfs(int k) {
    while (!g[k].empty()) {
        if (seen[g[k].back().second] == 1) {
           g[k].pop_back();
           continue; // if edge has already been deleted
        }
        seen[g[k].back().second] = 1;
        int a = g[k].back().first;
        g[k].pop_back();
        dfs(a);
    }
    seq.push_back(k);
}

signed main() {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);  
    	int n, m;
    	cin >> n >> m;
    	g = vector<vector<pair<int, int>>> (n);
        seen = vector<bool> (m, 0);
    	for (int i = 0; i < m; i++) {
    		int a, b;
    		cin >> a >> b;
    		a--; b--;
    		g[a].push_back({b, i});
    		g[b].push_back({a, i});
    	}
    	//dont need to check if possible bc question says is possible
        dfs(0);
    	
        vector<int> index(n, 0);
    	vector<pair<int, int>> groups; //end then start, should have soonest end points first, both values 1 more than real
    	for (int i = 0; i < seq.size(); i++) {
    		int a = seq[i];
    		if (index[a] != 0) { //used before
    			groups.push_back({i+1, index[a]});
    		}
            index[a] = i+1; //so even if just ended, need this
    	}
    	int lb = n; //leftmost which has been done
    	int rb = 0; //rightmost which has been done
    	for (auto x : groups) {
    		if (x.first-1 <= lb || x.second-1 >= rb || (x.second-1 <= lb && x.first-1 >= rb)) { //if no overlap --> if on left, if on right, if around
    			for (int i = x.second-1; i < x.first-1; i++) { //iterate over all spots
    				if (i < lb || i >= rb) { //so knot only appears once, and subroutes arent a part
    					cout << seq[i]+1 << " ";
    				}
    			}
    			cout << endl;
    			lb = x.second-1;
    			rb = x.first-1;
    		}
    	}		
    	
    }
     
    //WA, says some edges not used in third test case --> WTF, should not happen
     
    //all edges should be used in euler
    //then somehow vanish in process?

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:45:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |      for (int i = 0; i < seq.size(); i++) {
      |                      ~~^~~~~~~~~~~~

Subtask #1
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 904 KB Output is correct
5 Incorrect 1 ms 600 KB Edge does not exist or used 36, 28
6 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Incorrect 1 ms 604 KB Edge does not exist or used 36, 28
6 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Incorrect 2 ms 604 KB Edge does not exist or used 36, 28
6 Halted 0 ms 0 KB -