oj.uz

답안 #902258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
902258 2024-01-10T07:40:10 Z damamila 어르신 집배원 (BOI14_postmen) C++14
0 / 100
 1 ms 464 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	int n, m;
	cin >> n >> m;
	vector<set<int>> g(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].insert(b);
		g[b].insert(a);
	}
	//dont need to check if possible bc question says is possible
	for (int i = 0; i < n; i++) {
		while (g[i].size() > 0) {
			vector<int> seq;
			stack<int> stak;
			stak.push(i);
			while (!stak.empty()) {
				int u = stak.top();
				//~ cout << u+1 << endl;
				if (g[u].size() > 0) { //if still neighbours
					int v = *g[u].begin();
					stak.push(v);
					g[u].erase(v); //erase edge from both sides
					g[v].erase(u);
				} else { //need to add to tour
					stak.pop();
					seq.push_back(u);
					//~ cout << u+1 << " ";
				}
			}
			//~ cout << "seq " ;
			//~ for (int i : seq) {
				//~ cout << i+1 << " ";
			//~ }
			//~ cout << endl;
			//now make sure no vertices visited multiple times
			map<int, int> index;
			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] = 0;
				} else {
					index[a] = i+1; //so no confusion if in first position
				}
			}
			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; //all edges in this region should have been added
					rb = x.first-1;
				}
			}	
			//lb should be 0, and rb should be n(-1) by the end!!!! --> is this the case	
		}
	}
	
}

//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? --> WHERE

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:49:22: 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]
   49 |    for (int i = 0; i < seq.size(); i++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Incorrect 0 ms 348 KB Some edges were not used
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Some edges were not used
4 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 348 KB Output is correct
3 Incorrect 0 ms 348 KB Some edges were not used
4 Halted 0 ms 0 KB -