Submission #902387

#	Time	Username	Problem	Language	Result	Execution time	Memory
902387		damamila	Senior Postmen (BOI14_postmen)	C++14	0 / 100	3 ms	904 KiB

postmen

#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 (stderr)

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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45