oj.uz

답안 #420630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420630 2021-06-08T13:02:31 Z Peti Roller Coaster Railroad (IOI16_railroad) C++14
30 / 100
 311 ms 52768 KB 
#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

vector<vector<int>> g;
vector<bool> volt;

int bejar(int akt){
    volt[akt] = true;
    int ret = 1;
    for(int x : g[akt])
        if(!volt[x])
            ret += bejar(x);
    return ret;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();

    vector<int> compr;
    compr.reserve(2*n);
    for(int x : s)
        compr.push_back(x);
    for(int x : t)
        compr.push_back(x);

    sort(compr.begin(), compr.end());
    compr.erase(unique(compr.begin(), compr.end()), compr.end());

    vector<int> va(n), vb(n);
    for(int i = 0; i < n; i++){
        va[i] = lower_bound(compr.begin(), compr.end(), s[i])-compr.begin();
        vb[i] = lower_bound(compr.begin(), compr.end(), t[i])-compr.begin();
    }

    int m = (int)compr.size();
    vector<int> fok(m, 0);
    g.resize(m);
    for(int i = 0; i < n; i++){
        fok[va[i]]++;
        fok[vb[i]]--;
        g[va[i]].push_back(vb[i]);
    }

    fok[0]--;
    fok[m-1]++;

    for(int i = 0; i < m-1; i++){
        if(fok[i] < 0)
            g[i].push_back(i+1);
        if(fok[i] <= 0)
            fok[i+1] += fok[i];
        else
            return 1;
    }

    volt.assign(m, false);
    if(fok[m-1] == 0 && bejar(0) == m)
        return 0;
    return 1;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB n = 2
2 Correct 1 ms 204 KB n = 2
3 Correct 1 ms 292 KB n = 2
4 Correct 1 ms 204 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Incorrect 0 ms 204 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB n = 2
2 Correct 1 ms 204 KB n = 2
3 Correct 1 ms 292 KB n = 2
4 Correct 1 ms 204 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Incorrect 0 ms 204 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 311 ms 50360 KB n = 199999
2 Correct 214 ms 27628 KB n = 199991
3 Correct 227 ms 27704 KB n = 199993
4 Correct 214 ms 31172 KB n = 152076
5 Correct 121 ms 19636 KB n = 93249
6 Correct 294 ms 33348 KB n = 199910
7 Correct 271 ms 41540 KB n = 199999
8 Correct 252 ms 36320 KB n = 199997
9 Correct 269 ms 35704 KB n = 171294
10 Correct 197 ms 29164 KB n = 140872
11 Correct 284 ms 33732 KB n = 199886
12 Correct 273 ms 41676 KB n = 199996
13 Correct 258 ms 37428 KB n = 200000
14 Correct 205 ms 26576 KB n = 199998
15 Correct 223 ms 26288 KB n = 200000
16 Correct 205 ms 27052 KB n = 199998
17 Correct 195 ms 27640 KB n = 200000
18 Correct 204 ms 26216 KB n = 190000
19 Correct 227 ms 46804 KB n = 177777
20 Correct 128 ms 20972 KB n = 100000
21 Correct 289 ms 41916 KB n = 200000
22 Correct 238 ms 33880 KB n = 200000
23 Correct 310 ms 52768 KB n = 200000

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB n = 2
2 Correct 1 ms 204 KB n = 2
3 Correct 1 ms 292 KB n = 2
4 Correct 1 ms 204 KB n = 2
5 Correct 1 ms 204 KB n = 2
6 Incorrect 0 ms 204 KB answer is not correct: 1 instead of 523688153
7 Halted 0 ms 0 KB -