제출 #704033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704033		Abrar_Al_Samit	장난감 기차 (IOI17_train)	C++17	100 / 100	1642 ms	1656 KiB

train

#include<bits/stdc++.h>
#include "train.h"
using namespace std;

const int nax = 5000;
int n, m;
vector<int>g[nax], gt[nax];

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> u, vector<int> v) {
	n = A.size(), m = u.size();
	for(int i=0; i<m; ++i) {
		g[u[i]].push_back(v[i]);
		gt[v[i]].push_back(u[i]);
	}
	vector<int>nontrap(n), trap(n), need(n);

	int tt = n;
	while(tt--) {
		queue<int>q;
		for(int i=0; i<n; ++i) {
			need[i] = trap[i] = nontrap[i] = 0;
		}
		for(int i=0; i<n; ++i) {
			if(R[i]) nontrap[i] = 1, q.push(i);
			else trap[i] = 1;
		}

		for(int i=0; i<n; ++i) {
			if(nontrap[i]) continue;
			if(A[i]) need[i] = 1;
			else need[i] = g[i].size();
		}


		while(!q.empty()) {
			int v = q.front(); q.pop();
			trap[v] = 0, nontrap[v] = 1;
			for(int to : gt[v]) {
				if(--need[to]==0) {
					q.push(to);
				}
			}
		}

		for(int x=0; x<n; ++x) if(nontrap[x]) {
			bool all = true, one = false;
			for(int to : g[x]) {
				all &= trap[to];
				one |= trap[to];
			}

			if((A[x] && all) || (!A[x] && one)) {
				nontrap[x] = 0, trap[x] = 1, R[x] = 0;
			}
		}
	}
	return nontrap;
}

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