oj.uz

Submission #1068626

# Submission time Handle Problem Language Result Execution time Memory
1068626 2024-08-21T11:00:26 Z Abito Toy Train (IOI17_train) C++17
11 / 100
 1763 ms 1648 KB 
#include "train.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int N=5005;
int n,vis[N];
bool a[N],c[N],cyc[N],h;
vector<int> adj[N];
void dfs(int x){
	vis[x]=1;
	for (auto u:adj[x]){
		if (c[u]) continue;
		if (vis[u]==2) continue;
		if (vis[u]) h=1;
		else dfs(u);
	}vis[x]=2;
	return;
}
bool getans(int s){
	queue<int> q;
	q.push(s);
	vis[s]=1;
	bool ok=0;
	while (!q.empty()){
		int x=q.front();
		//cout<<x<<' ';
		q.pop();
		ok|=cyc[x];
		for (auto u:adj[x]){
			if (vis[u]) continue;
			else{
				vis[u]=1;
				q.push(u);
			}
		}
	}//cout<<endl;
	return ok;
}
std::vector<int32_t> who_wins(std::vector<int32_t> A, std::vector<int32_t> r, std::vector<int32_t> u, std::vector<int32_t> v) {
	n=A.size();
	for (int i=1;i<=n;i++) a[i]=A[i-1],c[i]=r[i-1];
	for (int i=0;i<u.size();i++){
		adj[u[i]+1].pb(v[i]+1);
	}
	vector<int> ans(n);
	for (int i=1;i<=n;i++){
		if (c[i]) continue;
		h=0;
		dfs(i);
		cyc[i]=h;
		memset(vis,0,sizeof(vis));
	}
	for (int i=1;i<=n;i++){
		ans[i-1]=!getans(i);
		memset(vis,0,sizeof(vis));
	}
	return ans;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 860 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 1368 KB Output is correct
2 Correct 108 ms 1116 KB Output is correct
3 Correct 85 ms 1112 KB Output is correct
4 Incorrect 1110 ms 1256 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 856 KB Output is correct
2 Correct 173 ms 1120 KB Output is correct
3 Correct 279 ms 1624 KB Output is correct
4 Correct 345 ms 1648 KB Output is correct
5 Correct 432 ms 1404 KB Output is correct
6 Correct 375 ms 1624 KB Output is correct
7 Correct 391 ms 1372 KB Output is correct
8 Correct 279 ms 1116 KB Output is correct
9 Correct 19 ms 1116 KB Output is correct
10 Correct 668 ms 1412 KB Output is correct
11 Correct 635 ms 1408 KB Output is correct
12 Correct 616 ms 1368 KB Output is correct
13 Correct 805 ms 1468 KB Output is correct
14 Correct 408 ms 1372 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1763 ms 1288 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 860 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -