oj.uz

Submission #580940

# Submission time Handle Problem Language Result Execution time Memory
580940 2022-06-22T06:37:18 Z Koosha_mv Toy Train (IOI17_train) C++14
11 / 100
 732 ms 1236 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#include "train.h"

const int N=5050;

int n,A[N],B[N],dp[N],pd[N];
vector<int> g[N];

void solve0(){
	f(t,0,n){
		f(u,0,n){
			int And=1,Or=0;
			for(auto v : g[u]){
				Or|=dp[v];
				And&=dp[v];
			}
			pd[u]=(dp[u] && ((A[u]==0 && Or) || (A[u]==1 && And)));
		}
		f(u,0,n) dp[u]=pd[u];
	} 
}
void solve1(){
	//dbga(dp,0,n);
	f(t,0,n){
		f(u,0,n){
			int And=1,Or=0;
			for(auto v : g[u]){
				Or|=dp[v];
				And&=dp[v];
			}
			pd[u]=(dp[u] || ((A[u]==0 && Or) || (A[u]==1 && And)));
		}
		f(u,0,n) dp[u]=pd[u];
	}
}
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v){
	f(i,0,u.size()) g[u[i]].pb(v[i]);
	n=a.size();
	f(i,0,n) A[i]=a[i],B[i]=r[i],dp[i]=B[i]^1;
	solve0();
	solve1();
	vector<int> ans(n);
	f(i,0,n) ans[i]=dp[i]^1;
	//dbgv(ans);
	return ans;
}

/*
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	who_wins({1,1},{1,0},{0,0,1,1},{0,1,0,1});
}*/

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:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   57 |  f(i,0,u.size()) g[u[i]].pb(v[i]);
      |    ~~~~~~~~~~~~                
train.cpp:57:2: note: in expansion of macro 'f'
   57 |  f(i,0,u.size()) g[u[i]].pb(v[i]);
      |  ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB 3rd lines differ - on the 4th token, expected: '0', found: '1'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 980 KB Output is correct
2 Correct 530 ms 1144 KB Output is correct
3 Correct 517 ms 1216 KB Output is correct
4 Correct 587 ms 1204 KB Output is correct
5 Correct 622 ms 1200 KB Output is correct
6 Correct 613 ms 1192 KB Output is correct
7 Correct 651 ms 1192 KB Output is correct
8 Correct 595 ms 1172 KB Output is correct
9 Correct 574 ms 1148 KB Output is correct
10 Correct 566 ms 1216 KB Output is correct
11 Correct 677 ms 1236 KB Output is correct
12 Correct 553 ms 1236 KB Output is correct
13 Correct 629 ms 1236 KB Output is correct
14 Correct 569 ms 1156 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 1108 KB Output is correct
2 Correct 634 ms 1108 KB Output is correct
3 Correct 717 ms 1096 KB Output is correct
4 Correct 538 ms 1028 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 273 ms 824 KB Output is correct
7 Correct 25 ms 996 KB Output is correct
8 Incorrect 25 ms 980 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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