# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
682117 | as111 | Traffic (CEOI11_tra) | C++14 | 247 ms | 23532 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <map>
#define MAXN 100000
using namespace std;
int N, M;
set<pair<int, int>> west;
set<int> east;
vector<int> adj[MAXN + 1];
vector<int> rev[MAXN + 1];
stack<int> S;
bool visited[MAXN + 1];
int ID[MAXN + 1];
vector<int> components[MAXN];
int numComponents;
int ans[MAXN + 1];
void dfs1(int x) {
visited[x] = true;
for (int i = 0; i < adj[x].size(); i++) {
if (!visited[adj[x][i]]) dfs1(adj[x][i]);
}
S.push(x);
}
void dfs2(int x) {
ID[x] = numComponents;
components[numComponents].push_back(x);
visited[x] = true;
if (east.count(x)) ans[ID[x]]++;
for (int i = 0; i < rev[x].size(); i++) {
if (!visited[rev[x][i]]) dfs2(rev[x][i]);
}
}
int main() {
int A, B;
cin >> N >> M >> A >> B;
for (int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
if (x == 0) {
west.insert({ -y,i });//dec y coords
}
if (x == A) {
east.insert(i);
}
}
for (int m = 0; m < M; m++) {
int a, b, k;
cin >> a >> b >> k;
adj[a].push_back(b);
rev[b].push_back(a);
if (k != 1) {
adj[b].push_back(a);
rev[a].push_back(b);
}
}
for (int i = 0; i < N; i++) {
if (!visited[i]) dfs1(i);
}
for (int i = 0; i < N; i++) {
visited[i] = false;
}
while (!S.empty()) {
int v = S.top();
S.pop();
if (!visited[v]) {
dfs2(v);
numComponents++;
}
}
for (auto e : west) {
cout << ans[ID[e.second]] << endl;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |