Submission #485474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485474	2021-11-08T00:47:19 Z	PedroBigMan	Toy Train (IOI17_train)	C++14	11 / 100	1481 ms	1928 KB

train

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include "train.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}

class DiGraph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<bool> visited;
  	ll target; 
	bool cycle;
	
    DiGraph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
    }
    
    void DFS(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {DFS(adj[s][i]);}
			else if(adj[s][i]==target) {cycle=true;}
        }
        return;
    }
};

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) 
{
 	ll N = a.size(); ll M = u.size();
	vector<vector<ll> > adj; REP(i,0,N) {adj.pb({});}
	REP(i,0,M) {adj[u[i]].pb(v[i]);}
	DiGraph G(adj);
	vector<bool> cycle; REP(i,0,N) {cycle.pb(false);}
	REP(i,0,N)
	{
		if(r[i]==0) {continue;}
		G.Reset(); G.cycle=false; G.target=i; G.DFS(i);
		cycle[i]=G.cycle;
	}
	vector<ll> ans; REP(i,0,N) {ans.pb(0);}
	REP(i,0,N)
	{
		G.Reset(); G.DFS(i); 
		REP(j,0,N) {if(cycle[j] && G.visited[j]) {ans[i]=1;}}
	}
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	1928 KB	Output is correct
2	Correct	280 ms	1908 KB	Output is correct
3	Correct	309 ms	1808 KB	Output is correct
4	Correct	1182 ms	1676 KB	Output is correct
5	Correct	774 ms	1804 KB	Output is correct
6	Correct	596 ms	1676 KB	Output is correct
7	Correct	866 ms	1804 KB	Output is correct
8	Correct	330 ms	1804 KB	Output is correct
9	Correct	306 ms	1804 KB	Output is correct
10	Correct	401 ms	1676 KB	Output is correct
11	Correct	350 ms	1680 KB	Output is correct
12	Correct	94 ms	1676 KB	Output is correct
13	Correct	935 ms	1804 KB	Output is correct
14	Correct	977 ms	1804 KB	Output is correct
15	Correct	941 ms	1804 KB	Output is correct
16	Correct	920 ms	1804 KB	Output is correct
17	Correct	920 ms	1804 KB	Output is correct
18	Correct	471 ms	1548 KB	Output is correct