답안 #117690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117690 2019-06-17T06:33:30 Z Plurm 장난감 기차 (IOI17_train) C++14
11 / 100
647 ms 1912 KB
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> g[5005];
vector<int> rg[5005];
bool found[5005];
stack<int> ord;
void dfs1(int u){
    if(found[u]) return;
    found[u] = true;
    for(int v : g[u]){
        dfs1(v);
    }
    ord.push(u);
}
int cc[5005];
int memcnt[5005];
bool gcc[5005];
void dfs2(int u, int c = 0){
    if(!found[u]) return;
    found[u] = false;
    cc[u] = c;
    memcnt[c]++;
    for(int v : rg[u]){
        dfs2(v, c);
    }
}
bool dfs3(int u){
    if(found[u]) return false;
    found[u] = true;
    for(int v : g[u]){
        if(dfs3(v)) return true;
    }
    return gcc[cc[u]];
}
bool loop[5005];
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    // Subtask 3
    int m = u.size();
    for(int i = 0; i < m; i++){
        g[u[i]].push_back(v[i]);
        rg[v[i]].push_back(u[i]);
        if(u[i] == v[i]) loop[u[i]] = true;
    }
    int n = a.size();
    for(int i = 0; i < n; i++){
        dfs1(i);
    }
    int cccnt = 0;
    while(!ord.empty()){
        int cur = ord.top();
        ord.pop();
        if(found[cur]) dfs2(cur, cccnt++);
    }
    vector<int> res;
    for(int i = 0; i < n; i++){
        if(r[i]){
            gcc[cc[i]] = memcnt[cc[i]] > 1 || loop[i];
        }
    }
    for(int i = 0; i < n; i++){
        memset(found, false, sizeof(found));
        res.push_back(dfs3(i));
    }
	return res;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 279 ms 1380 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 512 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 1788 KB Output is correct
2 Correct 266 ms 1792 KB Output is correct
3 Correct 228 ms 1912 KB Output is correct
4 Correct 58 ms 1792 KB Output is correct
5 Correct 279 ms 1784 KB Output is correct
6 Correct 647 ms 1784 KB Output is correct
7 Correct 13 ms 1664 KB Output is correct
8 Correct 163 ms 1784 KB Output is correct
9 Correct 368 ms 1784 KB Output is correct
10 Correct 134 ms 1644 KB Output is correct
11 Correct 186 ms 1600 KB Output is correct
12 Correct 28 ms 1576 KB Output is correct
13 Correct 42 ms 1792 KB Output is correct
14 Correct 68 ms 1792 KB Output is correct
15 Correct 39 ms 1792 KB Output is correct
16 Correct 51 ms 1792 KB Output is correct
17 Correct 38 ms 1792 KB Output is correct
18 Correct 427 ms 1612 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 1408 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 1564 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 279 ms 1380 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -