Submission #473447

#	Time	Username	Problem	Language	Result	Execution time	Memory
473447		elgamalsalman	Alternating Current (BOI18_alternating)	C++17	0 / 100	71 ms	17056 KiB

alternating

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef pair<int, int> ii;
typedef array<int, 3> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

int n, m, ind;
//vii splitIntervals;
viii intervals;
vvi adj;
bool isPossible = 1;
bitset<100050> visited, colours, directions;

void dfs(int u, int colour) { 
  visited[u] = 1;
  colours[u] = colour;

  for (int v : adj[u]) {
    if (!visited[v]) dfs(v, !colour);
    else if (colours[u] == colours[v]) isPossible = 0;
  }
}

bool sweepLine() {
  const int START = 0;
  const int END = 1;
  vvii track;
  track.assign(n + 20, vii());
  for (iii& interval : intervals) { 
    track[interval[0]].push_back({START, interval[2]});
    track[interval[1]].push_back({END, interval[2]});
  }

  set<int> currIntervals;
  for (int i = 0; i <= n; i++) {
    //=====Check if there are at least 2 and if there are exactly 2 tracks
    if (i) {
      if (currIntervals.size() < 2) isPossible = 0;
      else if (currIntervals.size() == 2) {
	auto it = currIntervals.begin();
	int u = *it;
	it++;
	int v = *it;

	adj[u].push_back(v);
	adj[v].push_back(u);
      }
    }

    for (ii& checkPoint : track[i]) {
      if (checkPoint.fi == START) currIntervals.insert(checkPoint.se);
      else currIntervals.erase(checkPoint.se);
    }
  }
}

void findSolution() {
  sort(intervals.begin(), intervals.end(), [](iii& ele1, iii& ele2) {
      if (ele1[0] < ele2[0]) return 1;
      else if (ele1[0] == ele2[0] && ele1[1] > ele2[1]) return 1;
      else return 0;
      });

  int s0 = 0, s1 = 0;
  for (iii& interval : intervals) {
    int start = interval[0], end = interval[1];
    if (start <= s0 && start <= s1) {
      if (s0 < s1) {
	s0 = max(s0, end);
	directions[interval[2]] = 0;
      } else {
	s1 = max(s1, end);
	directions[interval[2]] = 1;
      }
    } else if (start <= s0) {
	s0 = max(s0, end);
	directions[interval[2]] = 0;
    } else {
	s1 = max(s1, end);
	directions[interval[2]] = 1;
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  adj.assign(m + 20, vi());
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;

    if (b <= a) {
      //splitIntervals.push_back({ind, ind + 1});
      intervals.push_back({0, b, ind++});
      intervals.push_back({a, n, ind++});
    } else {
      intervals.push_back({a, b, ind++});
    }
  }

  sort(intervals.begin(), intervals.end());

  sweepLine();

  visited.reset();
  for (int i = 0; i <= m; i++) {
    if (!visited[i]) dfs(i, 0);
  }

  // =======verify splitIntervals=======
  //for (ii& splitInterval : splitIntervals) {
  //  if (colours[splitInterval.fi] != colours
  //}
  
  if (!isPossible) return cout << "impossible\n", 0;

  findSolution();

  for (int i = 0; i < m; i++) cout << directions[i];
  cout << '\n';
}

Compilation message (stderr)

alternating.cpp: In function 'bool sweepLine()':
alternating.cpp:64:1: warning: no return statement in function returning non-void [-Wreturn-type]
   64 | }
      | ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26