Submission #33246

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
33246	2017-10-23T04:36:22 Z	model_code	Toy Train (IOI17_train)	C++11	11 / 100	16 ms	3568 KB

train

#include "train.h"

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 5000+10;

const int B = 0;
const int A = 1;

bool win[MAXN], mark[MAXN];
int n_comp;
int comp[MAXN];
vector<int> r;
vector<int> order;
vector<int> adj[MAXN], bak[MAXN], q[MAXN];

void dfs(int v) {
    mark[v] = true;
    for (int i = 0; i < (int)adj[v].size(); i++) if (!mark[adj[v][i]])
        dfs(adj[v][i]);
    order.push_back(v);
}

void dfs2(int v, int id) {
    comp[v] = id;
    for (int i = 0; i < (int)bak[v].size(); i++) if (comp[bak[v][i]] == -1)
        dfs2(bak[v][i], id);
    if (r[v])
        win[id] = true;
    q[id].push_back(v);
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
    ::r = r;
    for (int i = 0; i < (int)u.size(); i++) {
        adj[u[i]].push_back(v[i]);
        bak[v[i]].push_back(u[i]);
    }
    int n = (int)a.size();
    for (int i = 0; i < n; i++) if (mark[i] == false)
        dfs(i);
    memset(comp, -1, sizeof comp);
    for (int i = n-1; i >= 0; i--) if (comp[order[i]] == -1) {
        dfs2(order[i], n_comp++);
        if (win[n_comp-1] && (int)q[n_comp-1].size() == 1) {
            win[n_comp-1] = false;
            for (int j = 0; j < (int)adj[order[i]].size(); j++)
                if (adj[order[i]][j] == order[i]) {
                    win[n_comp-1] = true;
                    break;
                }
        }
    }
	for (int i = n_comp-1; i >= 0; i--)
		for (int j = 0; j < (int)q[i].size(); j++)
			for (int k = 0; k < (int)adj[q[i][j]].size(); k++)
				win[comp[q[i][j]]] |= win[comp[adj[q[i][j]][k]]];
    vector<int> res;
    for (int i = 0; i < n; i++)
        res.push_back(win[comp[i]] ? A : B);
    return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	3324 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	2400 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	16 ms	3568 KB	Output is correct
2	Correct	9 ms	3568 KB	Output is correct
3	Correct	6 ms	3416 KB	Output is correct
4	Correct	16 ms	3448 KB	Output is correct
5	Correct	9 ms	3424 KB	Output is correct
6	Correct	6 ms	3424 KB	Output is correct
7	Correct	9 ms	3420 KB	Output is correct
8	Correct	6 ms	3424 KB	Output is correct
9	Correct	9 ms	3396 KB	Output is correct
10	Correct	13 ms	3396 KB	Output is correct
11	Correct	6 ms	3388 KB	Output is correct
12	Correct	9 ms	3384 KB	Output is correct
13	Correct	16 ms	3460 KB	Output is correct
14	Correct	6 ms	3460 KB	Output is correct
15	Correct	9 ms	3472 KB	Output is correct
16	Correct	9 ms	3464 KB	Output is correct
17	Correct	9 ms	3460 KB	Output is correct
18	Correct	6 ms	3240 KB	Output is correct