oj.uz

Submission #365318

# Submission time Handle Problem Language Result Execution time Memory
365318 2021-02-11T12:48:10 Z GioChkhaidze None (JOI16_ho_t3) C++14
26 / 100
 149 ms 23868 KB 
#include <bits/stdc++.h>
 
#define pb push_back
#define F first
#define S second
 
using namespace std;
 
const int N = 2e5 + 5;
 
int n, m, q, ans;
int in[N], d[N], a[N], b[N];
bool act[N], ed[N], used[N];
vector < pair < int , int > > v[N], g[N];
queue < int > qr;
 
void lazy(int x, int idx) {
	--in[x];
	ed[idx] = true;
	if (!in[x] && !used[x]) {
		++ans;
		used[x] = true;
		for (int i = 0; i < g[x].size(); ++i) {
			int to = g[x][i].F, id = g[x][i].S;
			if (ed[id]) continue;
			lazy(to, id);
		}
	}
}
 
main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; ++i) {
		cin >> a[i] >> b[i];
		v[a[i]].pb({b[i], i});
		v[b[i]].pb({a[i], i});
	}
	
	for (int i = 2; i <= n; ++i) {
		d[i] = 1e9;
	}
 
	qr.push(1);
	while (!qr.empty()) {
		int x = qr.front();
		qr.pop();
		
		for (int i = 0; i < v[x].size(); ++i) {
			int to = v[x][i].F, id = v[x][i].S;
			if (d[x] + 1 < d[to]) {
				d[to] = d[x] + 1;
				qr.push(to);
			}
			
			if (d[x] + 1 == d[to]) {
				g[x].pb({to, id});	
				act[id] = true;
				++in[to];
			}
		} 
	}
 
	for (int i = 1; i <= m; ++i) {
		if (d[a[i]] > d[b[i]]) swap(a[i], b[i]);
	}
 
	for (int i = 1; i <= q; ++i) {
		int x;
		cin >> x;
		
		if (act[x]) {
			lazy(b[x], x);
		}
 
		cout << ans << "\n";
	}
}

Compilation message

2016_ho_t3.cpp: In function 'void lazy(int, int)':
2016_ho_t3.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for (int i = 0; i < g[x].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~
2016_ho_t3.cpp: At global scope:
2016_ho_t3.cpp:31:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main () {
      |       ^
2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int i = 0; i < v[x].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 8 ms 9984 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 7 ms 9836 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 ms 9708 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 8 ms 9984 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 7 ms 9836 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 ms 9708 KB Output is correct
9 Correct 148 ms 23020 KB Output is correct
10 Correct 134 ms 23020 KB Output is correct
11 Correct 124 ms 22892 KB Output is correct
12 Correct 125 ms 23148 KB Output is correct
13 Correct 127 ms 23148 KB Output is correct
14 Correct 133 ms 23404 KB Output is correct
15 Correct 73 ms 22252 KB Output is correct
16 Correct 66 ms 19052 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 23172 KB Output is correct
2 Correct 140 ms 23276 KB Output is correct
3 Correct 88 ms 19936 KB Output is correct
4 Correct 133 ms 23148 KB Output is correct
5 Correct 126 ms 23436 KB Output is correct
6 Correct 119 ms 23484 KB Output is correct
7 Correct 66 ms 19052 KB Output is correct
8 Correct 68 ms 18924 KB Output is correct
9 Correct 44 ms 16604 KB Output is correct
10 Correct 41 ms 16992 KB Output is correct
11 Incorrect 149 ms 23868 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 8 ms 9984 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 7 ms 9836 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 ms 9708 KB Output is correct
9 Correct 148 ms 23020 KB Output is correct
10 Correct 134 ms 23020 KB Output is correct
11 Correct 124 ms 22892 KB Output is correct
12 Correct 125 ms 23148 KB Output is correct
13 Correct 127 ms 23148 KB Output is correct
14 Correct 133 ms 23404 KB Output is correct
15 Correct 73 ms 22252 KB Output is correct
16 Correct 66 ms 19052 KB Output is correct
17 Correct 138 ms 23172 KB Output is correct
18 Correct 140 ms 23276 KB Output is correct
19 Correct 88 ms 19936 KB Output is correct
20 Correct 133 ms 23148 KB Output is correct
21 Correct 126 ms 23436 KB Output is correct
22 Correct 119 ms 23484 KB Output is correct
23 Correct 66 ms 19052 KB Output is correct
24 Correct 68 ms 18924 KB Output is correct
25 Correct 44 ms 16604 KB Output is correct
26 Correct 41 ms 16992 KB Output is correct
27 Incorrect 149 ms 23868 KB Output isn't correct
28 Halted 0 ms 0 KB -