oj.uz

Submission #952857

# Submission time Handle Problem Language Result Execution time Memory
952857 2024-03-25T03:16:01 Z abczz Split the Attractions (IOI19_split) C++14
40 / 100
 164 ms 65232 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]) {
        C[v] = 1;
      }
      for (auto v : G[u]) {
        for (auto x : adj[v]) {
          if (C[x]) ++in[x];
        }
      }
      visited[G[u][0]] = 1;
      Q.push(G[u][0]);
      while (!P.empty() || !Q.empty()) {
        ll v;
        if (!P.empty()) {
          v = P.front();
          P.pop();
        }
        else {
          v = Q.front();
          Q.pop();
          if (marked[v]) continue;
        }
        marked[v] = 1;
        if (B[0] < A[0]) {
          ++B[0];
          F[v] = 0;
        }
        else F[v] = 2;
        dfs(v, 0);
        for (auto x : adj[v]) {
          if (C[x]) {
            --in[x];
            if (!marked[x] && in[x] == 1) {
              P.push(x);
              visited[x] = 1;
            }
            else if (!visited[x] && in[x] > 1) {
              Q.push(x);
              visited[x] = 1;
            }
          }
        }
      }
      for (int i=0; i<m; ++i) {
        if (!visited[i]) {
          while (true) {
            
          }
        }
      }
      for (int i=0; i<m; ++i) {
        if (F[i] != 0) visited[i] = 0;
      }
      for (auto v : G[u]) {
        if (F[v] == 2) {
          find(v, 1);
          break;
        }
      }
		}
    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:193:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |  for (int i=0; i<p.size(); ++i) {
      |                ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19544 KB ok, correct split
2 Correct 4 ms 19736 KB ok, correct split
3 Correct 4 ms 19548 KB ok, correct split
4 Correct 4 ms 19548 KB ok, correct split
5 Correct 4 ms 19544 KB ok, correct split
6 Correct 4 ms 19548 KB ok, correct split
7 Correct 154 ms 59340 KB ok, correct split
8 Correct 146 ms 65228 KB ok, correct split
9 Correct 145 ms 65232 KB ok, correct split
10 Correct 81 ms 42184 KB ok, correct split
11 Correct 81 ms 41968 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19548 KB ok, correct split
2 Correct 4 ms 19708 KB ok, correct split
3 Correct 4 ms 19548 KB ok, correct split
4 Correct 99 ms 40988 KB ok, correct split
5 Correct 117 ms 39824 KB ok, correct split
6 Correct 73 ms 41968 KB ok, correct split
7 Correct 140 ms 65228 KB ok, correct split
8 Correct 93 ms 36040 KB ok, correct split
9 Correct 62 ms 30304 KB ok, correct split
10 Correct 66 ms 38112 KB ok, correct split
11 Correct 62 ms 38344 KB ok, correct split
12 Correct 62 ms 38340 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19548 KB ok, correct split
2 Correct 104 ms 39732 KB ok, correct split
3 Correct 39 ms 28112 KB ok, correct split
4 Correct 4 ms 19548 KB ok, correct split
5 Correct 134 ms 48892 KB ok, correct split
6 Correct 164 ms 48724 KB ok, correct split
7 Correct 128 ms 48772 KB ok, correct split
8 Correct 143 ms 48916 KB ok, correct split
9 Correct 123 ms 48716 KB ok, correct split
10 Correct 29 ms 24656 KB ok, no valid answer
11 Correct 42 ms 27988 KB ok, no valid answer
12 Correct 83 ms 37068 KB ok, no valid answer
13 Correct 90 ms 37592 KB ok, no valid answer
14 Correct 59 ms 35948 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19548 KB ok, correct split
2 Correct 5 ms 17496 KB ok, no valid answer
3 Correct 5 ms 19548 KB ok, correct split
4 Correct 4 ms 19548 KB ok, correct split
5 Correct 4 ms 19544 KB ok, correct split
6 Correct 5 ms 19548 KB ok, correct split
7 Correct 4 ms 19548 KB ok, correct split
8 Correct 5 ms 19548 KB ok, correct split
9 Correct 6 ms 20060 KB ok, correct split
10 Correct 6 ms 20060 KB ok, correct split
11 Correct 5 ms 19548 KB ok, correct split
12 Incorrect 7 ms 20060 KB invalid split: #1=800, #2=1599, #3=2
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19544 KB ok, correct split
2 Correct 4 ms 19736 KB ok, correct split
3 Correct 4 ms 19548 KB ok, correct split
4 Correct 4 ms 19548 KB ok, correct split
5 Correct 4 ms 19544 KB ok, correct split
6 Correct 4 ms 19548 KB ok, correct split
7 Correct 154 ms 59340 KB ok, correct split
8 Correct 146 ms 65228 KB ok, correct split
9 Correct 145 ms 65232 KB ok, correct split
10 Correct 81 ms 42184 KB ok, correct split
11 Correct 81 ms 41968 KB ok, correct split
12 Correct 4 ms 19548 KB ok, correct split
13 Correct 4 ms 19708 KB ok, correct split
14 Correct 4 ms 19548 KB ok, correct split
15 Correct 99 ms 40988 KB ok, correct split
16 Correct 117 ms 39824 KB ok, correct split
17 Correct 73 ms 41968 KB ok, correct split
18 Correct 140 ms 65228 KB ok, correct split
19 Correct 93 ms 36040 KB ok, correct split
20 Correct 62 ms 30304 KB ok, correct split
21 Correct 66 ms 38112 KB ok, correct split
22 Correct 62 ms 38344 KB ok, correct split
23 Correct 62 ms 38340 KB ok, correct split
24 Correct 5 ms 19548 KB ok, correct split
25 Correct 104 ms 39732 KB ok, correct split
26 Correct 39 ms 28112 KB ok, correct split
27 Correct 4 ms 19548 KB ok, correct split
28 Correct 134 ms 48892 KB ok, correct split
29 Correct 164 ms 48724 KB ok, correct split
30 Correct 128 ms 48772 KB ok, correct split
31 Correct 143 ms 48916 KB ok, correct split
32 Correct 123 ms 48716 KB ok, correct split
33 Correct 29 ms 24656 KB ok, no valid answer
34 Correct 42 ms 27988 KB ok, no valid answer
35 Correct 83 ms 37068 KB ok, no valid answer
36 Correct 90 ms 37592 KB ok, no valid answer
37 Correct 59 ms 35948 KB ok, no valid answer
38 Correct 4 ms 19548 KB ok, correct split
39 Correct 5 ms 17496 KB ok, no valid answer
40 Correct 5 ms 19548 KB ok, correct split
41 Correct 4 ms 19548 KB ok, correct split
42 Correct 4 ms 19544 KB ok, correct split
43 Correct 5 ms 19548 KB ok, correct split
44 Correct 4 ms 19548 KB ok, correct split
45 Correct 5 ms 19548 KB ok, correct split
46 Correct 6 ms 20060 KB ok, correct split
47 Correct 6 ms 20060 KB ok, correct split
48 Correct 5 ms 19548 KB ok, correct split
49 Incorrect 7 ms 20060 KB invalid split: #1=800, #2=1599, #3=2
50 Halted 0 ms 0 KB -