oj.uz

Submission #60103

# Submission time Handle Problem Language Result Execution time Memory
60103 2018-07-23T16:25:41 Z Adhyyan1252 Ronald (COCI17_ronald) C++11
120 / 120
 166 ms 1636 KB 
#include<bits/stdc++.h>

using namespace std;

int n, m;
bool g[1003][1003];
int lead[1003];

void dfs(int cur, int l){
	lead[cur] = l;
	for(int i = 0; i < n; i++){
		if(g[cur][i] && lead[i] == -1){
			dfs(i, l);
		}
	}
}

int main(){
	cin>>n>>m;
	if(n == 2 && m == 0){
		cout<<"DA"<<endl;
		return 0;
	}else if(n > 2 && m == 0){
		cout<<"NE"<<endl;
		return 0;
	}
	for(int i = 0; i < m; i++){
		int a, b; cin>>a>>b; a--, b--;
		g[a][b] = g[b][a] = 1;
	}
	for(int i = 0; i < n; i++){
		lead[i] = -1;
		g[i][i] = true;
	}
	vector<int> leads;
	for(int i = 0; i < n; i++){
		if(lead[i] == -1){
			dfs(i, i);
			leads.push_back(i);
		}
	}
	if(leads.size() != 2){
		cout<<"NE"<<endl;
		return 0;
	}
	bool pos = true;
	for(int i = 0; i < n && pos; i++){
		for(int j = 0; j < n; j++){
			//cout<<i<<" , "<<j<<" "<<lead[j]<<" "<<lead[i]<<" "<<g[j][i]<<endl;
			if((lead[j] == lead[i])^(g[j][i])){
				pos = false; break;
			}
		}
	}
	if(pos) cout<<"DA"<<endl;
	else cout<<"NE"<<endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 520 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 3 ms 692 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 692 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 2 ms 736 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 2 ms 740 KB Output is correct
4 Correct 3 ms 740 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 3 ms 740 KB Output is correct
4 Correct 3 ms 740 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 740 KB Output is correct
2 Correct 4 ms 740 KB Output is correct
3 Correct 4 ms 740 KB Output is correct
4 Correct 5 ms 740 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 792 KB Output is correct
2 Correct 39 ms 1048 KB Output is correct
3 Correct 14 ms 1048 KB Output is correct
4 Correct 11 ms 1048 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1048 KB Output is correct
2 Correct 26 ms 1048 KB Output is correct
3 Correct 104 ms 1636 KB Output is correct
4 Correct 166 ms 1636 KB Output is correct