oj.uz

Submission #473462

# Submission time Handle Problem Language Result Execution time Memory
473462 2021-09-15T14:46:01 Z elgamalsalman Alternating Current (BOI18_alternating) C++17
19 / 100
 48 ms 5360 KB 
#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);
    }
  }
}

bool 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;
    }
  }

  return (s0 == n && s1 == n);
}

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
  //}
  
  isPossible = findSolution();

  if (!isPossible) return cout << "impossible\n", 0;

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

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB no wires in direction 1 between segments 1 and 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB no wires in direction 1 between segments 1 and 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB no wires in direction 1 between segments 1 and 6
4 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4476 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 17 ms 2888 KB Output is correct
4 Correct 23 ms 2888 KB Output is correct
5 Correct 42 ms 5196 KB Output is correct
6 Correct 38 ms 5260 KB Output is correct
7 Correct 40 ms 5212 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 47 ms 5316 KB Output is correct
11 Correct 33 ms 4480 KB Output is correct
12 Correct 38 ms 5060 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 48 ms 5268 KB Output is correct
16 Correct 15 ms 2972 KB Output is correct
17 Correct 45 ms 5360 KB Output is correct
18 Correct 46 ms 5072 KB Output is correct
19 Correct 3 ms 588 KB Output is correct
20 Correct 46 ms 5188 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB no wires in direction 1 between segments 1 and 6
4 Halted 0 ms 0 KB -