oj.uz

답안 #1061380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1061380 2024-08-16T08:29:33 Z vjudge1 장난감 기차 (IOI17_train) C++17
0 / 100
 5 ms 1628 KB 
#include <bits/stdc++.h>
#include "train.h"
 
using namespace std;
 
const int M = 5000;

vector<int> nei[M],dd;
int vis[M],low[M],ind[M],t;
stack<int> st;
bool ch[M],cy[M];

void dfs(int u)
{
	vis[u]=1;
	low[u]=ind[u]=t++;
	st.push(u);
	for (int i:nei[u])
		if (!vis[i])
		{
			dfs(i);
			low[u]=min(low[u],low[i]);
		}
		else if(vis[i]==1)
			low[u]=min(low[u],low[i]);
	if (low[u]==ind[u])
	{
		vector<int> v;
		while (st.top()!=u)
			v.push_back(st.top()),vis[st.top()]=2,st.pop();
		v.push_back(st.top()),vis[st.top()]=2;
		st.pop();
		for (int i:v)
			if (ch[i])
			{
				if (v.size()>1 or cy[i])
					dd.push_back(i);
			}
	}
}

void dfs1(int u)
{
	vis[u]=1;
	for (int i:nei[u])
		if (!vis[i])
			dfs1(i);
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n=a.size(),m=u.size();
	for (int i=0;i<n;i++)
		ch[i]=r[i];
	for (int i=0;i<m;i++)
	{
		nei[u[i]].push_back(v[i]);
		if (u[i]==v[i])
			cy[u[i]]=1;
	}
	for (int i=0;i<n;i++)
		if (!vis[i])
			dfs(i);
	for (int i=0;i<n;i++)
		vis[i]=0;
	for (int i:dd)
		if (!vis[i])
			dfs1(i);
	vector<int> ans(n);
	for (int i=0;i<n;i++)
		if (vis[i])
			ans[i]=1;
	return ans;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1628 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1628 KB Output is correct
2 Correct 4 ms 1528 KB Output is correct
3 Correct 4 ms 1372 KB Output is correct
4 Incorrect 5 ms 1628 KB 3rd lines differ - on the 13th token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1372 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1368 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1628 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -