oj.uz

Submission #197864

# Submission time Handle Problem Language Result Execution time Memory
197864 2020-01-23T18:01:12 Z triplem5ds Teoretičar (COCI18_teoreticar) C++14
130 / 130
 5757 ms 94324 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 26 ms 23800 KB Output is correct
3 Correct 25 ms 23800 KB Output is correct
4 Correct 26 ms 23800 KB Output is correct
5 Correct 26 ms 23800 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23800 KB Output is correct
2 Correct 25 ms 23800 KB Output is correct
3 Correct 26 ms 23800 KB Output is correct
4 Correct 25 ms 23800 KB Output is correct
5 Correct 26 ms 23800 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24384 KB Output is correct
2 Correct 33 ms 24312 KB Output is correct
3 Correct 35 ms 24568 KB Output is correct
4 Correct 30 ms 24312 KB Output is correct
5 Correct 31 ms 24440 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24312 KB Output is correct
2 Correct 27 ms 24376 KB Output is correct
3 Correct 35 ms 24568 KB Output is correct
4 Correct 32 ms 24568 KB Output is correct
5 Correct 30 ms 24304 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1058 ms 52864 KB Output is correct
2 Correct 4803 ms 77104 KB Output is correct
3 Correct 1835 ms 65184 KB Output is correct
4 Correct 1154 ms 74016 KB Output is correct
5 Correct 979 ms 66508 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 52584 KB Output is correct
2 Correct 1863 ms 64948 KB Output is correct
3 Correct 2459 ms 70252 KB Output is correct
4 Correct 1115 ms 72136 KB Output is correct
5 Correct 216 ms 37436 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2255 ms 60504 KB Output is correct
2 Correct 3295 ms 71508 KB Output is correct
3 Correct 165 ms 30972 KB Output is correct
4 Correct 1229 ms 84420 KB Output is correct
5 Correct 433 ms 57048 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1533 ms 94324 KB Output is correct
2 Correct 5150 ms 78632 KB Output is correct
3 Correct 2894 ms 73176 KB Output is correct
4 Correct 1643 ms 88552 KB Output is correct
5 Correct 1115 ms 82680 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1161 ms 77436 KB Output is correct
2 Correct 5757 ms 82664 KB Output is correct
3 Correct 3868 ms 74720 KB Output is correct
4 Correct 1657 ms 88224 KB Output is correct
5 Correct 1232 ms 83924 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1176 ms 77052 KB Output is correct
2 Correct 5514 ms 82160 KB Output is correct
3 Correct 2875 ms 70120 KB Output is correct
4 Correct 256 ms 40356 KB Output is correct
5 Correct 1248 ms 83172 KB Output is correct