제출 #409537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409537		Kevin_Zhang_TW	장난감 기차 (IOI17_train)	C++17	0 / 100	8 ms	1828 KiB

train

#include <bits/stdc++.h>
#include "train.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
void debug(auto l, auto r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 5005;

int n;
vector<int> edge[MAX_N], rev_edge[MAX_N];
vector<pair<int,int>> alle;
bool rm[MAX_N], is_a[MAX_N], vis[MAX_N];

int out_deg[MAX_N];

void dfs1(int x) {
	if (rm[x] || vis[x]) return;
	vis[x] = true;
	for (int u : rev_edge[x]) {
		if (is_a[u] || --out_deg[u] == 0)
			dfs1(u);
	}
}

void dfs2(int x) {
	if (rm[x] || vis[x]) return;
	vis[x] = true;
	for (int u : rev_edge[x]) {
		if (!is_a[u] || --out_deg[u] == 0)
			dfs2(u);
	}
}

void init_g() {
	fill(out_deg, out_deg + n, 0);
	fill(vis, vis + n, false);
	for (auto [a, b] : alle) {
		if (rm[a] || rm[b]) continue;
		++out_deg[a];
	}
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	n = a.size();
	for (int i = 0;i < u.size();++i) {
		alle.pb(v[i], u[i]);
		rev_edge[v[i]].pb(u[i]);
	}
	vector<int> res(n);

	for (int i = 0;i < n;++i)
		is_a[i] = a[i];

	int node_cnt = n;
	while (node_cnt) {
		init_g();
		for (int i = 0;i < n;++i) if (!rm[i]) {
			if (r[i] == 1) dfs1(i);
		}
		if (count(vis, vis + n, true) == node_cnt) {
			for (int i = 0;i < n;++i)
				if (!rm[i]) res[i] = 1;
			break;
		}
		vector<int> bwin;
		for (int i = 0;i < n;++i) if (!rm[i]) {
			if (!vis[i]) bwin.pb(i);
		}
		init_g();
		for (int i : bwin) dfs2(i);
		for (int i = 0;i < n;++i) if (!rm[i]) {
			if (vis[i] == true) {
				rm[i] = true;
				--node_cnt;
			}
		}
	}

	return res;
}

컴파일 시 표준 에러 (stderr) 메시지

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0;i < u.size();++i) {
      |                 ~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51