Submission #406832

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
406832	2021-05-18T05:51:54 Z	daniel920712	Toy Train (IOI17_train)	C++14	11 / 100	1110 ms	25556 KB

train

#include "train.h"
#include <stdio.h>

using namespace std;
vector < int > Next[5005],Next2[5005],ans,P,W;
bool have1[5005][5005];
bool can[5005];
bool have2[5][5005];
bool vis[5005];
bool F(int st,int here,int deg)
{

    int ok=0,t;
    vis[here]=1;
    if(here==st&&deg) return 1;
    if(have1[st][here]) return can[here];
    have1[st][here]=1;
    for(auto i:Next[here])
    {
        t=F(st,i,deg+1);
        if(W[here]==t) ok=1;
    }
    if(ok) can[here]=W[here];
    else can[here]=1-W[here];
    return can[here];

}
void F2(int here,int xx)
{
    if(have2[xx][here]) return;
    have2[xx][here]=1;
    for(auto i:Next2[here]) F2(i,xx);
}
vector < int > who_wins(vector < int > who, vector < int > power, vector < int > u, vector < int > v)
{
    P=power;
    W=who;
    int N=who.size(),M=u.size(),i;
	for(i=0;i<N;i++) ans.push_back(0);
	for(i=0;i<M;i++) Next[u[i]].push_back(v[i]);
	for(i=0;i<M;i++) Next2[v[i]].push_back(u[i]);
    for(i=0;i<N;i++) if(power[i]) F(i,i,0);
    for(i=0;i<N;i++) if(vis[i]) F2(i,can[i]);
    //for(i=0;i<N;i++) if(!vis[i]) F2(i,can[i]);


    for(i=0;i<N;i++)
    {
        if(have2[0][i]&&have2[1][i]) ans[i]=who[i];
        else if(have2[1][i]) ans[i]=1;
        else ans[i]=0;
    }
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	5872 KB	Output is correct
2	Correct	45 ms	9664 KB	Output is correct
3	Correct	107 ms	13232 KB	Output is correct
4	Correct	437 ms	12064 KB	Output is correct
5	Correct	69 ms	4404 KB	Output is correct
6	Correct	128 ms	5248 KB	Output is correct
7	Correct	341 ms	18584 KB	Output is correct
8	Correct	9 ms	1484 KB	Output is correct
9	Correct	8 ms	1356 KB	Output is correct
10	Correct	12 ms	1656 KB	Output is correct
11	Correct	9 ms	1356 KB	Output is correct
12	Correct	9 ms	1580 KB	Output is correct
13	Correct	10 ms	1820 KB	Output is correct
14	Correct	10 ms	1868 KB	Output is correct
15	Correct	10 ms	1820 KB	Output is correct
16	Correct	11 ms	1848 KB	Output is correct
17	Correct	10 ms	1868 KB	Output is correct
18	Correct	304 ms	18792 KB	Output is correct