Submission #72610

#	Time	Username	Problem	Language	Result	Execution time	Memory
72610		tamtam	Toy Train (IOI17_train)	C++14	0 / 100	2061 ms	2940 KiB

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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51