Submission #72610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72610	2018-08-26T11:34:35 Z	tamtam	Toy Train (IOI17_train)	C++14	0 / 100	2000 ms	2940 KB

train

#include "train.h"
#include <bits/stdc++.h>
#define F first
#define S second
typedef long long ll;
using namespace std;
int n,m;
int ans[5010];
int owner[5010];
vector<int> v[5010];
vector<int> charge;
int en;
int vis[5010];
int dp[5010];

int Solve(int nod){
	//cout <<nod<<"-"<<endl;
	if (vis[nod]){
		if (nod==en){
            return 1;
		}
		return dp[nod];
	}
	vis[nod]=1;
	int res=0;
	if (owner[nod]){
		res=0;
		for (int i=0;i<v[nod].size();i++){
			res|=Solve(v[nod][i]);
		}
	}else {
		res=1;
		//cout <<nod<<": ASD:\n";

		for (int i=0;i<v[nod].size();i++){
	//		cout <<v[nod][i]<<endl;
			int z=Solve(v[nod][i]);
//			cout <<nod<<" :"<<z<<endl;
		//	cout <<nod<<" :ASDF\n";
		}
	}
	return dp[nod]=res;
}

void track (int nod){
	//cout <<nod<<" ;\n";
	if (dp[nod]==4){
        return;
	}
	dp[nod]=100;
    ans[nod]=1;
    if (nod==en){
        dp[nod]=4;
    }
	for (int i=0;i<v[nod].size();i++){
		if (dp[v[nod][i]]==1||v[nod][i]==en){
			track(v[nod][i]);
		}
	}

}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> z) {
	n=a.size();m=u.size();
	for (int i=0;i<n;i++){
		owner[i]=a[i];
		if (r[i])charge.push_back(i);
	}
    for (int i=0;i<m;i++){
		v[u[i]].push_back(z[i]);
    }
    for (int i=0;i<charge.size();i++){
		memset(vis,0,sizeof vis);
		memset(dp,0,sizeof dp);
		en=charge[i];
		//cout <<"------------\n";
		if (Solve(charge[i])){
			//cout <<"============\n";
			track(charge[i]);
		}
    }
    vector<int > res;
    for (int i=0;i<n;i++){
		res.push_back(ans[i]);
    }
	return res;
}

Compilation message

train.cpp: In function 'int Solve(int)':
train.cpp:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0;i<v[nod].size();i++){
                ~^~~~~~~~~~~~~~
train.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0;i<v[nod].size();i++){
                ~^~~~~~~~~~~~~~
train.cpp:37:8: warning: unused variable 'z' [-Wunused-variable]
    int z=Solve(v[nod][i]);
        ^
train.cpp: In function 'void track(int)':
train.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<v[nod].size();i++){
               ~^~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<charge.size();i++){
                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	339 ms	1272 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	Incorrect	3 ms	1272 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1552 KB	Output is correct
2	Correct	50 ms	2032 KB	Output is correct
3	Correct	91 ms	2372 KB	Output is correct
4	Incorrect	675 ms	2676 KB	3rd lines differ - on the 13th token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-