oj.uz

Submission #60101

# Submission time Handle Problem Language Result Execution time Memory
60101 2018-07-23T16:24:14 Z Adhyyan1252 Ronald (COCI17_ronald) C++11
105 / 120
 224 ms 1608 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(m == 1 || (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
0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
15.0 / 15.0

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

Subtask #6
15.0 / 15.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 764 KB Output is correct
2 Correct 42 ms 1124 KB Output is correct
3 Correct 17 ms 1124 KB Output is correct
4 Correct 14 ms 1124 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1124 KB Output is correct
2 Correct 41 ms 1148 KB Output is correct
3 Correct 105 ms 1604 KB Output is correct
4 Correct 224 ms 1608 KB Output is correct