| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 115341 | 2019-06-06T17:42:07 Z | model_code | Traffic (CEOI11_tra) | C++17 | 5000 ms | 41936 KB |
/* Slower solution of TRA/jlac012
* A bin-search solution.
* Author: Tomasz Kociumaka, reusing some code by Mateusz Baranowski
*
*/
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define pb push_back
#define MAXN 300001
typedef pair<int, int> PII;
int n, m, A, B;
int i, l;
int tmp1, tmp2;
vector<PII> west, east; /* junctions on west riverbank */
vector<int> edges[MAXN], revedges[MAXN]; /* junctions in road network */
int eastern[MAXN]; /* equals 1 when junction lies on the east bank */
size_t visited[MAXN];
bool any[MAXN];
void read_input() {
scanf ("%d %d %d %d", &n, &m, &A, &B);
for (i = 1; i <= n; ++i) {
scanf ("%d %d", &tmp1, &tmp2);
eastern[i] = 0;
if (tmp1 == 0) west.pb(make_pair(tmp2, i));
else if (tmp1 == A) {
east.pb(make_pair(tmp2, i));
eastern[i] = 1;
}
}
sort(west.begin(), west.end());
sort(east.begin(), east.end());
for (size_t s = 0; s < east.size(); ++s) {
eastern[east[s].second] = s+1;
}
while (m-->0) {
scanf ("%d %d %d", &tmp1, &tmp2, &i);
edges[tmp1].pb(tmp2);
revedges[tmp2].pb(tmp1);
if (i == 2) {
edges[tmp2].pb(tmp1);
revedges[tmp1].pb(tmp2);
}
}
}
pair<int, int> reachable(int v, size_t s) {
size_t j;
int result = 0;
int mx = 0;
queue<int> q;
q.push(v);
while (!q.empty()) {
i = q.front(); q.pop();
result += (eastern[i] != 0);
mx = max(eastern[i], mx);
for (j = 0; j < edges[i].size(); ++j) {
l = edges[i][j];
if (visited[l] != s) { visited[l] = s; q.push(l); }
}
}
return make_pair(result, mx);
}
void generate_output() {
for (i = 1; i <= n; ++i) visited[i] = 0;
queue<int> Q;
for (i = 0; i < (int) east.size(); ++i) {
Q.push(east[i].second);
visited[east[i].second] = 1;
}
while (!Q.empty()) {
i = Q.front(); Q.pop();
// printf("in %d\n", i);
for (size_t j = 0; j < revedges[i].size(); ++j) {
l = revedges[i][j];
if (visited[l] != 1) { visited[l] = 1; Q.push(l); }
}
}
for (i = 0; i < (int) west.size(); ++i) {
any[i] = (visited[west[i].second] == 1);
// printf("%d: %d\n", i, any[i]);
}
for (i = 1; i <= n; ++i) visited[i] = 0;
int s = (int) west.size();
PII cur, prev = make_pair(-1, -1);
int delta = 1;
int ph = 0;
while(true) {
++ph;
if (s-delta>=0) {
if (!any[s-delta]) --delta;
if (delta == 0) {
printf("0\n");
delta = 1;
--s;
continue;
}
// printf("%d %d\n", s, delta);
cur = reachable(west[s-delta].second, ph);
if (cur == prev) {
for (i=0; i<delta; ++i) printf("%d\n",(any[s-i-1])?cur.first:0);
s -= delta;
delta *= 2;
} else {
if (delta > 1) delta /= 2;
else {
printf("%d\n", cur.first);
prev = cur;
--s;
}
}
} else if (delta > 1){
delta /= 2;
} else break;
}
}
int main() {
read_input();
generate_output();
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 14464 KB | Output is correct |
| 2 | Correct | 14 ms | 14464 KB | Output is correct |
| 3 | Correct | 12 ms | 14464 KB | Output is correct |
| 4 | Correct | 14 ms | 14464 KB | Output is correct |
| 5 | Correct | 13 ms | 14464 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 14464 KB | Output is correct |
| 2 | Correct | 14 ms | 14464 KB | Output is correct |
| 3 | Correct | 14 ms | 14464 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 14464 KB | Output is correct |
| 2 | Correct | 14 ms | 14484 KB | Output is correct |
| 3 | Correct | 14 ms | 14464 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 16 ms | 14668 KB | Output is correct |
| 2 | Correct | 84 ms | 14908 KB | Output is correct |
| 3 | Correct | 17 ms | 14720 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 29 ms | 15360 KB | Output is correct |
| 2 | Execution timed out | 5030 ms | 17900 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 66 ms | 17144 KB | Output is correct |
| 2 | Execution timed out | 5038 ms | 18972 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 127 ms | 19492 KB | Output is correct |
| 2 | Execution timed out | 5086 ms | 21200 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 208 ms | 21212 KB | Output is correct |
| 2 | Execution timed out | 5076 ms | 21544 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 288 ms | 24596 KB | Output is correct |
| 2 | Execution timed out | 5105 ms | 26476 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 461 ms | 30200 KB | Output is correct |
| 2 | Execution timed out | 5012 ms | 33712 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1261 ms | 41936 KB | Output is correct |
| 2 | Execution timed out | 5021 ms | 34892 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 257 ms | 24256 KB | Output is correct |
| 2 | Execution timed out | 5056 ms | 36044 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |