oj.uz

Submission #197377

# Submission time Handle Problem Language Result Execution time Memory
197377 2020-01-20T16:03:54 Z Neklixx Usmjeri (COCI17_usmjeri) C++14
28 / 140
 193 ms 9416 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define sh cin.tie(0); cin.sync_with_stdio(0); cout.tie(0);
#define FILE freopen("test.in", "r", stdin);
#define vprint(v) for (int ii = 0; ii < v.size(); ii++){cout << v[ii] << " ";}
#define debugv(v) if (v.size() != 0) {cout << "[ "; for (int __ = 0; __ < (int)(v.size()) - 1; __++){cout << v[__] << ", ";} cout << v[(int)(v.size()) - 1] << " ]" << endl;} else {cout << "[]" << endl;}
#define debug cout << "-----------------------------------------------" << endl;
#define print1(a) cout << "{ " << a << " }" << endl;
#define print2(a, b) cout << "{ " << a << ", " << b << " }" << endl;
#define print3(a, b, c) cout << "{ " << a << ", " << b << ", " << c << " }" << endl;
#define print4(a, b, c, d) cout << "{ " << a << ", " << b << ", " << c << ", " << d << " }" << endl;
using namespace std;
//#define int long long
const int INF = 1e9 + 228;
const int MAXN = 1e5 + 228;
const int mod = 1e9 + 7;
signed main()
{
#ifdef LOCAL
    FILE;
#endif
    sh;
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n - 1; i++) {
		int aa, bb;
		cin >> aa >> bb;
	}   
	vector<pair<int, int>> v; 
	for (int i = 0; i < m; i++) {
		int aa, bb;
		cin >> aa >> bb;
		aa--;
		bb--;
		if (aa > bb) 
			swap(aa, bb);
		v.pb({aa, 1});
		v.pb({bb, -1});
	}
	sort(all(v));
	int lst = 0;
	int bal = 0;
	int ans = 1;
	for (int i = 0; i < v.size();) {
		int now = v[i].F;
		if (bal == 0) {
			for (int j = 0; j < now - lst; j++) {
				ans *= 2;
				ans %= mod;
			}
		}
		while (i < v.size() && v[i].F == now) {
			bal += v[i].S;
			i++;
		}
		if (bal == 0) {
			lst = now;
			ans *= 2;
			ans %= mod;
		}
	}

		if (bal == 0) {
			for (int j = 0; j < n - 1 - lst; j++) {
				ans *= 2;
				ans %= mod;
			}
		}
		cout << ans << endl;
    return 0;
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size();) {
                  ~~^~~~~~~~~~
usmjeri.cpp:56:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (i < v.size() && v[i].F == now) {
          ~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 5068 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 9416 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 9256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 9184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 9180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 9372 KB Output isn't correct
2 Halted 0 ms 0 KB -