oj.uz

Submission #650265

# Submission time Handle Problem Language Result Execution time Memory
650265 2022-10-13T09:33:02 Z kingfran1907 Traffic (CEOI11_tra) C++14
100 / 100
 1025 ms 117176 KB 
#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

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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 52084 KB Output is correct
2 Correct 27 ms 52172 KB Output is correct
3 Correct 25 ms 52124 KB Output is correct
4 Correct 27 ms 52188 KB Output is correct
5 Correct 25 ms 52152 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 52152 KB Output is correct
2 Correct 28 ms 52112 KB Output is correct
3 Correct 28 ms 52180 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 52164 KB Output is correct
2 Correct 26 ms 52136 KB Output is correct
3 Correct 27 ms 52180 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 52304 KB Output is correct
2 Correct 43 ms 52688 KB Output is correct
3 Correct 28 ms 52556 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 53864 KB Output is correct
2 Correct 84 ms 57004 KB Output is correct
3 Correct 59 ms 55464 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 56084 KB Output is correct
2 Correct 114 ms 60096 KB Output is correct
3 Correct 86 ms 58212 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 59472 KB Output is correct
2 Correct 172 ms 65668 KB Output is correct
3 Correct 295 ms 68272 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 61944 KB Output is correct
2 Correct 202 ms 65500 KB Output is correct
3 Correct 346 ms 69344 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 66612 KB Output is correct
2 Correct 343 ms 75644 KB Output is correct
3 Correct 547 ms 83452 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 74588 KB Output is correct
2 Correct 544 ms 90300 KB Output is correct
3 Correct 611 ms 84296 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 870 ms 92344 KB Output is correct
2 Correct 568 ms 91880 KB Output is correct
3 Correct 1025 ms 106120 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 66240 KB Output is correct
2 Correct 566 ms 97212 KB Output is correct
3 Correct 905 ms 98868 KB Output is correct
4 Correct 1006 ms 117176 KB Output is correct