Submission #555330

#	Time	Username	Problem	Language	Result	Execution time	Memory
555330		Mamedov	Usmjeravanje (COCI22_usmjeravanje)	C++17	0 / 110	0 ms	212 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct edge {
  int x, y, id;
};

bool cmp(edge e1, edge e2) {
  if (e1.x == e2.x) {
    return e1.y > e2.y;
  } else {
    return e1.x < e2.x;
  }
}

vector<vector<int>>g, gp;
vector<bool>visited;
vector<int>order;

void dfs1(int node){
  visited[node] = true;
  for (int to : g[node]) {
    if (!visited[to]) {
      dfs1(to);
    }
  }
  order.eb(node);
}

void dfs2(int node) {
  visited[node] = true;
  for (int to : gp[node]) {
    if (!visited[to]) {
      dfs2(to);
    }
  }
}

void solve() {
  int a, b, m;
  cin >> a >> b >> m;
  vector<edge>E(m);
  for (int i = 0; i < m; ++i) {
    cin >> E[i].x >> E[i].y;
    E[i].id = i;
  }
  sort(all(E), cmp);
  g.resize(a + b + 1);
  gp.resize(a + b + 1);
  for (int i = 1; i < a; ++i) {
    g[i].eb(i + 1);
  }
  for (int i = a + 1; i < a + b; ++i) {
    g[i].eb(i + 1);
  }
  int maxY = 0;
  vector<char>res(m);
  for (edge e : E) {
    if (e.y <= maxY) {
      res[e.id] = '0';
      g[e.x].eb(a + e.y);
    } else {
      res[e.id] = '1';
      g[a + e.y].eb(e.x);
      maxY = e.y;
    }
  }
  for (int i = 1; i <= a + b; ++i) {
    for (int to : g[i]) {
      gp[to].eb(i);
    }
  }
  visited.assign(a + b + 1, false);
  for (int i = 1; i <= a + b; ++i) {
    if (!visited[i]) {
      dfs1(i);
    }
  }
  reverse(all(order));
  visited.assign(a + b + 1, false);
  int compos = 0;
  for (int i : order) {
    if (!visited[i]) {
      dfs2(i);
      ++compos;
    }
  }
  cout << compos << ln;
  for (char c : res) {
    cout << c << ' ';
  }
  cout << ln;
}
int main() {
  ios_base::sync_with_stdio(false);

  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60