Submission #126751

#	Time	Username	Problem	Language	Result	Execution time	Memory
126751		neki	Toy Train (IOI17_train)	C++14	5 / 100	2051 ms	1668 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define maxn 5010

#define loop(i, a, b) for(int i=a;i<b;i++)
#define cc(a) cout<< a << endl;
using namespace std;


vector<int> edges[maxn];
vector<int> owner;vector<int> power;
int low[maxn];
int bval[maxn];
int cnt=0;

bool dfs(int u){
    low[u]=cnt; if(power[u]) cnt++;
    bval[u]=0;
    bool ans=(!(owner[u]));
    for(auto&& e:edges[u]){
        bool cmp;
        if(bval[e]==-1) dfs(e);
        if(low[e]!=-1 and( low[e]!=low[u] or power[u])) cmp=1;
        else{ cmp=bval[e];}
        
        if(owner[u]) ans=ans or cmp;
        else ans=ans and cmp;
    }
    bval[u]=ans;
    low[u]=-1;
    return ans;
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int n=a.size();
	std::vector<int> res(n);
	loop(i, 0, u.size()) edges[u[i]].push_back(v[i]);
	owner=a;power=r;
	loop(i, 0, n){
	    loop(j, 0, n) {low[j]=-1;bval[j]=-1;}
	    res[i]=dfs(i);
	}
	
	return res;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:5:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define loop(i, a, b) for(int i=a;i<b;i++)
train.cpp:37:7:
  loop(i, 0, u.size()) edges[u[i]].push_back(v[i]);
       ~~~~~~~~~~~~~~                
train.cpp:37:2: note: in expansion of macro 'loop'
  loop(i, 0, u.size()) edges[u[i]].push_back(v[i]);
  ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51