제출 #197864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197864		triplem5ds	Teoretičar (COCI18_teoreticar)	C++14	130 / 130	5757 ms	94324 KiB

teoreticar

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i,a,b)  for(int i = a; i < b; i++)
#define endl '\n'

using ll = long long;
using db = long double;
using ii = pair<int, int>;

const int N = 1e6 + 5, LG = 19, MOD = 1e9 + 7;
const int SQ =320;
const long double EPS = 1e-7;
int deg[N];
int n, m, cnt;
ii edges[N];
vector<ii> adj[N];
bool vis[N];
int ans[N];
void dfs(int node, bool depth, vector<int> & l, vector<int> &r){
  while(adj[node].size()){
    auto e = adj[node].back();  adj[node].pop_back();
    int to = e.F;
    int eIndex = e.S;
    if(!vis[eIndex]){
        vis[eIndex] = true;
        if(depth)r.pb(eIndex);
        else
          l.pb(eIndex);
        deg[node]--;
        deg[to]--;
        dfs(to, depth ^ 1, l, r);
        break;
    }
  }

}
void solve(vector<int> e){
  if(e.empty())return;
  bool finale = true;
  vector<int> vt;
  for(auto i : e){
    int u = edges[i].F;
    int v = edges[i].S;
    if(!deg[u])vt.pb(u);
    if(!deg[v])vt.pb(v);
    deg[u]++;
    deg[v]++;
    if(deg[u] > 1 || deg[v] > 1)
      finale = false;
    adj[u].pb(ii(v, i));
    adj[v].pb(ii(u, i));
  }

  if(finale){
    cnt++;
    for(auto i : e)
      ans[i] = cnt;
     for(auto x : vt){
    deg[x] = 0;
    adj[x].clear();
  }
  for(auto x : e){
    vis[x] = false;
  }
    return;
  }
  vector<int> l, r;
  for(auto i : vt)
  if(deg[i] & 1){
    dfs(i, 0, l, r);
  }
  for(auto i : vt)
    while(deg[i])
      dfs(i, 0, l, r);

  for(auto x : vt){
    deg[x] = 0;
    adj[x].clear();
  }
  for(auto x : e){
    vis[x] = false;
  }
  solve(l);
  solve(r);
}
int32_t main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif

  int x;
  cin >> n >> x >> m;

  vector<int> v;

  f(i,0,m){
    cin >> edges[i].F >> edges[i].S;
    edges[i].S += n;
    v.pb(i);
  }

  solve(v);

  cout << cnt << '\n';
  f(i,0,m)
    cout << ans[i] << '\n';


  return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13