답안 #485474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
485474	2021-11-08T00:47:19 Z	PedroBigMan	장난감 기차 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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