oj.uz

답안 #107225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107225 2019-04-22T17:08:44 Z eriksuenderhauf Mergers (JOI19_mergers) C++11
0 / 100
 399 ms 263168 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
int deg[MAXN], col[MAXN], lo[MAXN], disc[MAXN];
int ind[MAXN];
pii edg[MAXN];
vii adj[MAXN];
int t = 0, vis[MAXN], cnt = 0, br[MAXN];

void dfs(int u, int p) {
	disc[u] = lo[u] = t++;
	vis[u] = 1;
	for (pii nx: adj[u]) {
		int v, id; tie(v, id) = nx;
		if (!vis[v]) {
			dfs(v, id);
			lo[u] = min(lo[u], lo[v]);
			if (disc[u] < lo[v])
				br[id] = 1;
		} else if (id != p)
			lo[u] = min(lo[u], disc[v]);
	}
}

int curC = 0;

void bfs(int cur) {
	deque<int> pq;
	pq.pb(cur);
	vis[cur] = 1;
	while (!pq.empty()) {
		int u = pq.front(); pq.pop_front();
		ind[u] = curC;
		vis[u] = 1;
		for (pii nx: adj[u]) {
			int v, id; tie(v, id) = nx;
			if (!br[id] && !vis[v])
				pq.pb(v);
		}
	}
	curC++;
}

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		edg[i] = {--u, --v};
	}
	for (int i = 0; i < n; i++) {
		ni(col[i]); --col[i];
	}
	for (int i = 1; i < n; i++) {
		int u, v; tie(u, v) = edg[i];
		u = col[u], v = col[v];
		if (u == v) continue;
		adj[u].pb({v, cnt});
		adj[v].pb({u, cnt});
		cnt++;
	}
	dfs(0, -1);
	mem(vis,0);
	for (int i = 0; i < k; i++)
		if (!vis[i])
			bfs(i);
	for (int i = 0; i < k; i++) {
		for (pii nx: adj[i]) {
			int u, id; tie(u, id) = nx;
			if (!br[id]) continue;
			deg[u]++;
		}
	}
	int lvs = 0;
	for (int i = 0; i < k; i++)
		if (deg[i] == 1)
			lvs++;
	pri((lvs+1)/2);
    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
mergers.cpp:85:3: note: in expansion of macro 'ni'
   ni(col[i]); --col[i];
   ^~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 27776 KB Output is correct
2 Correct 28 ms 27776 KB Output is correct
3 Correct 28 ms 27768 KB Output is correct
4 Correct 27 ms 27776 KB Output is correct
5 Correct 32 ms 27776 KB Output is correct
6 Correct 28 ms 27852 KB Output is correct
7 Correct 31 ms 27776 KB Output is correct
8 Correct 29 ms 27768 KB Output is correct
9 Correct 31 ms 27812 KB Output is correct
10 Correct 29 ms 27776 KB Output is correct
11 Correct 38 ms 27768 KB Output is correct
12 Correct 32 ms 27768 KB Output is correct
13 Incorrect 29 ms 27896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 27776 KB Output is correct
2 Correct 28 ms 27776 KB Output is correct
3 Correct 28 ms 27768 KB Output is correct
4 Correct 27 ms 27776 KB Output is correct
5 Correct 32 ms 27776 KB Output is correct
6 Correct 28 ms 27852 KB Output is correct
7 Correct 31 ms 27776 KB Output is correct
8 Correct 29 ms 27768 KB Output is correct
9 Correct 31 ms 27812 KB Output is correct
10 Correct 29 ms 27776 KB Output is correct
11 Correct 38 ms 27768 KB Output is correct
12 Correct 32 ms 27768 KB Output is correct
13 Incorrect 29 ms 27896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 27776 KB Output is correct
2 Correct 28 ms 27776 KB Output is correct
3 Correct 28 ms 27768 KB Output is correct
4 Correct 27 ms 27776 KB Output is correct
5 Correct 32 ms 27776 KB Output is correct
6 Correct 28 ms 27852 KB Output is correct
7 Correct 31 ms 27776 KB Output is correct
8 Correct 29 ms 27768 KB Output is correct
9 Correct 31 ms 27812 KB Output is correct
10 Correct 29 ms 27776 KB Output is correct
11 Correct 38 ms 27768 KB Output is correct
12 Correct 32 ms 27768 KB Output is correct
13 Incorrect 29 ms 27896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 399 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 27776 KB Output is correct
2 Correct 28 ms 27776 KB Output is correct
3 Correct 28 ms 27768 KB Output is correct
4 Correct 27 ms 27776 KB Output is correct
5 Correct 32 ms 27776 KB Output is correct
6 Correct 28 ms 27852 KB Output is correct
7 Correct 31 ms 27776 KB Output is correct
8 Correct 29 ms 27768 KB Output is correct
9 Correct 31 ms 27812 KB Output is correct
10 Correct 29 ms 27776 KB Output is correct
11 Correct 38 ms 27768 KB Output is correct
12 Correct 32 ms 27768 KB Output is correct
13 Incorrect 29 ms 27896 KB Output isn't correct
14 Halted 0 ms 0 KB -