oj.uz

Submission #60099

# Submission time Handle Problem Language Result Execution time Memory
60099 2018-07-23T16:22:57 Z Adhyyan1252 Ronald (COCI17_ronald) C++11
105 / 120
 231 ms 6152 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){
		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 248 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 3 ms 360 KB Output is correct
2 Correct 3 ms 472 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 628 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 628 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 636 KB Output is correct
4 Correct 2 ms 640 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 644 KB Output is correct
2 Correct 3 ms 648 KB Output is correct
3 Correct 3 ms 652 KB Output is correct
4 Correct 2 ms 656 KB Output is correct

Subtask #5
15.0 / 15.0

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

Subtask #6
15.0 / 15.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1024 KB Output is correct
2 Correct 51 ms 1736 KB Output is correct
3 Correct 27 ms 1736 KB Output is correct
4 Correct 18 ms 1860 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1860 KB Output is correct
2 Correct 48 ms 2400 KB Output is correct
3 Correct 163 ms 4244 KB Output is correct
4 Correct 231 ms 6152 KB Output is correct