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 <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 1e6+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
int n, m, A, B;
int x[maxn], y[maxn];
vector< int > graph[maxn], graph2[maxn];
vector< int > v;
int col[maxn];
pair<int, int> dp[maxn];
vector< pair<int, int> > edg;
bool bio[maxn];
void add(int a, int b) {
graph[a].push_back(b);
graph2[b].push_back(a);
edg.push_back({a, b});
}
void dfs(int x) {
col[x] = 1;
for (int tren : graph[x]) {
if (col[tren] == 0) dfs(tren);
}
v.push_back(x);
}
void dfs2(int x, int c) {
col[x] = c;
for (int tren : graph2[x])
if (col[tren] == -1) dfs2(tren, c);
}
void dfs3(int x) {
bio[x] = true;
for (int tren : graph[x])
if (!bio[tren]) dfs3(tren);
}
bool cmp(int a, int b) {
return y[a] < y[b];
}
pair<int, int> merg(pair<int, int> a, pair<int, int> b) {
if (a.X == -1) return b;
if (b.X == -1) return a;
return {min(a.X, b.X), max(a.Y, b.Y)};
}
int main() {
scanf("%d%d%d%d", &n, &m, &A, &B);
for (int i = 1; i <= n; i++)
scanf("%d%d", x+i, y+i);
for (int i = 0; i < m; i++) {
int a, b, k;
scanf("%d%d%d", &a, &b, &k);
add(a, b);
if (k == 2) add(b, a);
}
for (int i = 1; i <= n; i++)
if (!col[i]) dfs(i);
reverse(v.begin(), v.end());
memset(col, -1, sizeof col);
vector< int > t;
for (int tren : v) {
if (col[tren] == -1) {
dfs2(tren, tren);
t.push_back(tren);
}
}
//for (int i = 1; i <= n; i++) printf("%d ", col[i]); printf("\n");
for (int i = 1; i <= n; i++) graph[i].clear();
for (auto iter : edg) {
int x = iter.X;
int y = iter.Y;
if (col[x] != col[y])
graph[col[x]].push_back(col[y]);
}
memset(bio, false, sizeof bio);
for (int i = 1; i <= n; i++)
if (x[i] == 0 && !bio[col[i]]) dfs3(col[i]);
vector< int > ed;
for (int i = 1; i <= n; i++) {
if (x[i] == A && bio[col[i]]) {
ed.push_back(i);
}
}
for (int i = 1; i <= n; i++) dp[i] = {-1, -1};
sort(ed.begin(), ed.end(), cmp);
for (int i = 0; i < ed.size(); i++) {
int tr = col[ed[i]];
dp[tr] = merg(dp[tr], {i, i});
}
reverse(t.begin(), t.end());
for (int tren : t) {
for (int ac : graph[tren])
dp[tren] = merg(dp[tren], dp[ac]);
}
ed.clear();
for (int i = 1; i <= n; i++) {
if (x[i] == 0) ed.push_back(i);
}
sort(ed.begin(), ed.end(), cmp);
reverse(ed.begin(), ed.end());
for (int tren : ed) {
pair<int, int> out = dp[col[tren]];
if (out.X == -1) printf("0\n");
else printf("%d\n", out.Y - out.X + 1);
}
return 0;
}
Compilation message (stderr)
tra.cpp: In function 'int main()':
tra.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int i = 0; i < ed.size(); i++) {
| ~~^~~~~~~~~~~
tra.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d%d%d%d", &n, &m, &A, &B);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d%d", x+i, y+i);
| ~~~~~^~~~~~~~~~~~~~~~~~
tra.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d%d%d", &a, &b, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |