oj.uz

Submission #952924

# Submission time Handle Problem Language Result Execution time Memory
952924 2024-03-25T05:13:03 Z abczz Split the Attractions (IOI19_split) C++14
33 / 100
 150 ms 62524 KB 
#include "split.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long
 
using namespace std;
 
vector <ll> V;
vector <ll> adj[100000], E[200000];
bool ap[200000], ok;
vector <ll> G[200000], X[100000];
bool visited[100000], marked[100000];
array<ll, 2> T[3];
queue <ll> Q, P;
ll m, k, A[3], B[3], in[100000], low[100000], st[100000], sz[200000], F[200000], C[200000], cnt;
 
void tar(ll u, ll p) {
	V.push_back(u);
	low[u] = st[u] = ++cnt;
	ll rch = 0;
	for (auto v : adj[u]) {
		if (!st[v]) {
			++rch;
			tar(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] >= st[u]) {
				if (p != -1) ap[u] = 1;
				while (!V.empty()) {
					auto x = V.back();
					V.pop_back();
					X[x].push_back(k);
					G[k].push_back(x);
					if (x == v) break;
				}
				X[u].push_back(k);
				G[k].push_back(u);
				++k;
			}
		}
		else if (v != p) {
			low[u] = min(low[u], st[v]);
		}
	}
	if (p == -1 & rch > 1) ap[u] = 1;
}
 
void dfs(ll u, ll w) {
  visited[u] = 1;
  for (auto v : adj[u]) {
    if (!visited[v] && !C[v]) {
      if (B[w] < A[w]) {
        F[v] = w;
        ++B[w];
      }
      else F[v] = 2;
      dfs(v, w);
    }
  }
}
 
void find(ll u, ll w) {
  if (B[w] < A[w]) {
    ++B[w];
    F[u] = w;
  }
  else F[u] = 2;
  dfs(u, w);
  for (auto v : adj[u]) {
    if (C[v] && !visited[v]) {
      find(v, w);
    }
  }
}
 
void solve(ll u, ll p) {
	if (ap[u]) ++sz[u];
	else sz[u] += G[u].size() - E[u].size();
	ll mx = -1;
	for (auto v : E[u]) {
		if (v != p) {
			solve(v, u);
			sz[u] += sz[v];
			mx = max(mx, sz[v]);
		}
	}
	mx = max(mx, m - sz[u]);
	if (!ok && !ap[u] && mx <= m-A[0]) {
		if (mx >= A[1]) {
			if (m-sz[u] == mx) {
				F[p] = 1;
			}
			else {
				for (auto v : E[u]) {
					if (v != p) {
						if (sz[v] == mx) {
							F[v] = 1;
							break;
						}
					}
				}
			}
      for (auto v : G[u]) {
        C[v] = 1;
      }
      for (auto v : G[u]) {
        if (F[v]) {
          ++B[1];
          dfs(v, 1);
        }
      }
      for (auto v : G[u]) {
        if (!F[v]) {
          find(v, 0);
          break;
        }
      }
		}
		else {
      for (auto v : G[u]) {
        if (B[0] < A[0]) {
          ++B[0];
          F[v] = 0;
          dfs(v, 0);
        }
        else if (B[1] < A[1]) {
          ++B[1];
          F[v] = 1;
          dfs(v, 0);
        }
        else {
          F[v] = 2;
          dfs(v, 0);
        }
      }
		}
    ok = 1;
    return;
	}
}
 
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	A[0] = T[0][0] = a, A[1] = T[1][0] = b, A[2] = T[2][0] = c;
  T[1][1] = 1, T[2][1] = 2;
	sort(A, A+3);
  sort(T, T+3);
	m = n;
	k = n;
	for (int i=0; i<p.size(); ++i) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	tar(0, -1);
	for (int i=0; i<n; ++i) {
		if (ap[i]) {
			for (auto u : X[i]) {
				E[i].push_back(u);
				E[u].push_back(i);
			}
		}
	}
  solve(n, -1);
  vector <int> U;
  if (ok) {
    U.clear();
    for (int i=0; i<n; ++i) {
      U.push_back(T[F[i]][1]+1);
    }
  }
  else {
    for (int i=0; i<n; ++i) {
      U.push_back(F[i]);
    }
  }
	return U;
}

Compilation message

split.cpp: In function 'void tar(long long int, long long int)':
split.cpp:47:8: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   47 |  if (p == -1 & rch > 1) ap[u] = 1;
      |      ~~^~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:151:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |  for (int i=0; i<p.size(); ++i) {
      |                ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19544 KB ok, correct split
2 Correct 5 ms 19548 KB ok, correct split
3 Correct 8 ms 19548 KB ok, correct split
4 Correct 4 ms 19544 KB ok, correct split
5 Correct 7 ms 19736 KB ok, correct split
6 Incorrect 5 ms 19544 KB invalid split: #1=40, #2=1, #3=59
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB ok, correct split
2 Correct 6 ms 19728 KB ok, correct split
3 Correct 4 ms 19548 KB ok, correct split
4 Correct 103 ms 41600 KB ok, correct split
5 Correct 118 ms 40396 KB ok, correct split
6 Correct 95 ms 42152 KB ok, correct split
7 Correct 142 ms 62524 KB ok, correct split
8 Correct 114 ms 36812 KB ok, correct split
9 Correct 60 ms 30936 KB ok, correct split
10 Correct 65 ms 38320 KB ok, correct split
11 Correct 63 ms 38344 KB ok, correct split
12 Correct 62 ms 38600 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19548 KB ok, correct split
2 Correct 111 ms 40200 KB ok, correct split
3 Correct 37 ms 28156 KB ok, correct split
4 Correct 4 ms 19544 KB ok, correct split
5 Correct 144 ms 48076 KB ok, correct split
6 Correct 150 ms 47504 KB ok, correct split
7 Correct 128 ms 47440 KB ok, correct split
8 Correct 129 ms 47824 KB ok, correct split
9 Correct 128 ms 47512 KB ok, correct split
10 Correct 29 ms 24656 KB ok, no valid answer
11 Correct 48 ms 27984 KB ok, no valid answer
12 Correct 90 ms 37564 KB ok, no valid answer
13 Correct 100 ms 37928 KB ok, no valid answer
14 Correct 67 ms 36492 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB ok, correct split
2 Correct 4 ms 17500 KB ok, no valid answer
3 Correct 6 ms 19736 KB ok, correct split
4 Correct 5 ms 19544 KB ok, correct split
5 Incorrect 5 ms 19548 KB invalid split: #1=11, #2=1, #3=4
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19544 KB ok, correct split
2 Correct 5 ms 19548 KB ok, correct split
3 Correct 8 ms 19548 KB ok, correct split
4 Correct 4 ms 19544 KB ok, correct split
5 Correct 7 ms 19736 KB ok, correct split
6 Incorrect 5 ms 19544 KB invalid split: #1=40, #2=1, #3=59
7 Halted 0 ms 0 KB -