oj.uz

Submission #42364

# Submission time Handle Problem Language Result Execution time Memory
42364 2018-02-26T13:48:30 Z nickyrio 버스 (JOI14_bus) C++14
35 / 100
 1000 ms 35372 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

using namespace std;

struct edge {
    int a, b, x, y;
}g[N];
vector<int> e[N];
int d[N], visited[N];
int n, m;

void Enter() {
  	IO;
    cin >> n >> m;
    REP(i, m) {
        cin >> g[i].a >> g[i].b >> g[i].x >> g[i].y;
        e[g[i].a].push_back(i);
    }
}
bool disabled[N];

void dfs(int u, int isEdge, int MAX, int now) {
    if (isEdge) {
        visited[u] = true;
        d[u] = MAX;
        if (!disabled[g[u].b]) dfs(g[u].b, 0, MAX, now);
    }
    else {
      	bool stop = true;
        for (int id : e[u]) {
            if (visited[id] == false) {
                if (g[id].x >= now) {
                    dfs(id, 1, MAX, g[id].y);
                }
              	stop = false;
            }
        }
      if (stop) disabled[u] = true;
    }
}

vector<pp> res;

void Process() {
    sort(e[1].begin(), e[1].end(), [] (const int &a, const int &b) {
         return g[a].x > g[b].x;
    });
    for (int id : e[1]) {
        if (visited[id] == false) {
            dfs(id, 1, g[id].x, g[id].y);
        }
    }
    REP(i, m) {
        if (g[i].b == n && visited[i]) {
            res.push_back(pp(g[i].y, d[i]));
        }
    }
    sort(res.begin(), res.end());
    REP(i, res.size()) if (i) {
        res[i].second = max(res[i].second, res[i - 1].second);
    }
}

void Query() {
    int q;
    cin >> q;
    REP(i, q) {
        int x;
        cin >> x;
        int pos = upper_bound(res.begin(), res.end(), pp(x + 1, -1)) - res.begin() - 1;
        if (pos < 0) cout << -1 << '\n';
        else cout << res[pos].second << '\n';
    }
}
int main() {
    Enter();
    Process();
    Query();
}

Compilation message

bus.cpp: In function 'void Process()':
bus.cpp:4:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i, a) for (int i = 0; i<a; ++i)
                                    ^
bus.cpp:71:5: note: in expansion of macro 'REP'
     REP(i, res.size()) if (i) {
     ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 25 ms 24032 KB Output is correct
3 Correct 22 ms 24032 KB Output is correct
4 Correct 23 ms 24032 KB Output is correct
5 Correct 22 ms 24036 KB Output is correct
6 Correct 25 ms 24036 KB Output is correct
7 Correct 21 ms 24060 KB Output is correct
8 Correct 21 ms 24112 KB Output is correct
9 Correct 23 ms 24112 KB Output is correct
10 Correct 25 ms 24188 KB Output is correct
11 Correct 21 ms 24188 KB Output is correct
12 Correct 21 ms 24188 KB Output is correct
13 Correct 21 ms 24284 KB Output is correct
14 Correct 23 ms 24284 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24284 KB Output is correct
2 Correct 43 ms 24924 KB Output is correct
3 Correct 43 ms 24924 KB Output is correct
4 Correct 25 ms 24924 KB Output is correct
5 Correct 30 ms 24924 KB Output is correct
6 Correct 29 ms 24924 KB Output is correct
7 Correct 39 ms 24924 KB Output is correct
8 Correct 21 ms 24924 KB Output is correct
9 Correct 39 ms 24924 KB Output is correct
10 Correct 48 ms 24952 KB Output is correct
11 Correct 42 ms 24952 KB Output is correct
12 Correct 48 ms 25116 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 34464 KB Output is correct
2 Correct 242 ms 34464 KB Output is correct
3 Correct 221 ms 34464 KB Output is correct
4 Correct 210 ms 34464 KB Output is correct
5 Correct 215 ms 34464 KB Output is correct
6 Correct 238 ms 34664 KB Output is correct
7 Correct 190 ms 34664 KB Output is correct
8 Correct 210 ms 34664 KB Output is correct
9 Correct 223 ms 34732 KB Output is correct
10 Execution timed out 1066 ms 34732 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 34860 KB Output is correct
2 Correct 234 ms 34860 KB Output is correct
3 Correct 249 ms 34988 KB Output is correct
4 Correct 232 ms 35120 KB Output is correct
5 Correct 240 ms 35120 KB Output is correct
6 Correct 241 ms 35228 KB Output is correct
7 Correct 217 ms 35228 KB Output is correct
8 Correct 229 ms 35372 KB Output is correct
9 Correct 256 ms 35372 KB Output is correct
10 Execution timed out 1072 ms 35372 KB Time limit exceeded
11 Halted 0 ms 0 KB -