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
#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++){
                  ~^~~~~~~~~~~~~~
# 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 -
# 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 -
# 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 -
# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 2676 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2940 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 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 -