oj.uz

Submission #255936

# Submission time Handle Problem Language Result Execution time Memory
255936 2020-08-02T06:13:47 Z 임성재(#5031) Joker (BOI20_joker) C++17
0 / 100
 2000 ms 13928 KB 
#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const long long INF = 1e18;
const int inf = 1e9;

int n, m, q;
int l, r;
vector<pii> e;
vector<pii> g[200010];
int d[200010];

bool dfs(int x) {
	for(auto i : g[x]) {
		if(l <= i.se  && i.se <= r) continue;
		if(d[i.fi]) {
			if(d[x] - d[i.fi] % 2 == 0) {
				return true;
			}

			continue;
		}

		d[i.fi] = d[x] + 1;
		if(dfs(i.fi)) return true;
	}

	return false;
}

int main() {
	fast;

	cin >> n >> m >> q;

	for(int i=1; i<=m; i++) {
		int u, v;

		cin >> u >> v;

		e.eb(u, v);
	}

	//reverse(all(e));

	for(int i=0; i<e.size(); i++) {
		g[e[i].fi].eb(e[i].se, i+1);
		g[e[i].se].eb(e[i].fi, i+1);
	}

	while(q--) {
		cin >> l >> r;

		bool flag = false;

		for(int i=1; i<=n; i++) {
			d[i] = 0;
		}

		for(int i=1; i<=n; i++) {
			if(!d[i]) {
				d[i] = 1;
				if(dfs(i)) flag = true;
			}
		}

		if(flag) cout << "YES\n";
		else cout << "NO\n";
	}
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<e.size(); i++) {
               ~^~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Incorrect 4 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Incorrect 4 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Execution timed out 2090 ms 13928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Incorrect 4 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Incorrect 4 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Incorrect 4 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -