oj.uz

Submission #485476

# Submission time Handle Problem Language Result Execution time Memory
485476 2021-11-08T00:53:11 Z PedroBigMan Toy Train (IOI17_train) C++14
11 / 100
 1842 ms 2500 KB 
#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> > adj1,adj2; REP(i,0,N) {adj1.pb({}); adj2.pb({});}
	REP(i,0,M) {adj1[u[i]].pb(v[i]); if(r[u[i]]==0 && r[v[i]]==0) {adj2[u[i]].pb(v[i]);}}
	DiGraph G1(adj1); DiGraph G2(adj2);
	vector<bool> cycle; REP(i,0,N) {cycle.pb(false);}
	REP(i,0,N)
	{
		G2.Reset(); G2.cycle=false; G2.target=i; G2.DFS(i);
		cycle[i]=G2.cycle;
	}
	vector<ll> ans; REP(i,0,N) {ans.pb(1);}
	REP(i,0,N)
	{
		G1.Reset(); G1.DFS(i); 
		REP(j,0,N) {if(cycle[j] && G1.visited[j]) {ans[i]=0;}}
	}
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 2412 KB Output is correct
2 Correct 396 ms 2252 KB Output is correct
3 Correct 407 ms 2240 KB Output is correct
4 Incorrect 1357 ms 2016 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 1596 KB Output is correct
2 Correct 335 ms 2124 KB Output is correct
3 Correct 492 ms 2296 KB Output is correct
4 Correct 580 ms 2100 KB Output is correct
5 Correct 711 ms 2420 KB Output is correct
6 Correct 587 ms 2460 KB Output is correct
7 Correct 614 ms 2324 KB Output is correct
8 Correct 466 ms 2244 KB Output is correct
9 Correct 141 ms 1868 KB Output is correct
10 Correct 941 ms 2040 KB Output is correct
11 Correct 942 ms 1940 KB Output is correct
12 Correct 943 ms 1960 KB Output is correct
13 Correct 1064 ms 2500 KB Output is correct
14 Correct 653 ms 2252 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1842 ms 2184 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 270 ms 1680 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -