oj.uz

답안 #515901

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
515901 2022-01-20T05:24:53 Z ac2hu Tales of seafaring (POI13_mor) C++14
100 / 100
 1635 ms 55660 KB 
#include <bits/stdc++.h>
using namespace std;
void setIO(string name) {
	#ifdef DEBUG
	#else 
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
	#endif
}
signed main(){
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int n,m,k;cin >> n >> m >> k;
	vector<int> adj[n];
	for(int i = 0;i<m;i++){
		int a,b;cin >> a >> b;
		a--;b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	string ans[k];
	struct queries{
		int b,d,i;
	};	
	vector<queries> qq[n];
	for(int i = 0;i<k;i++){
		int a,b,d;cin >> a >> b >> d;
		a--;b--;
		qq[a].push_back({b,d,i});
	}
	for(int i = 0;i<n;i++){
		int dist[n][2];
		for(int j = 0;j<n;j++)
			dist[j][0] = dist[j][1] = 1e9 + 10;
		queue<pair<int,int>> q;
		dist[i][0] = 0;
		q.push({i,0});
		while(!q.empty()){
			pair<int,int> x = q.front();
			q.pop();
			for(auto e : adj[x.first]){
				if(dist[e][(x.second + 1)%2] > dist[x.first][x.second] + 1){
					dist[e][(x.second + 1)%2] = dist[x.first][x.second] + 1;
					q.push({e,(x.second + 1)%2});
				}
			}
		}
		for(auto e : qq[i]){
			// if(e.i == 3){
			// 	cout << i << " " << e.b << " " << e.d << "\n";
			// 	for(int i = 0;i<n;i++)
			// 		cout << dist[i][0] << " " << dist[i][1] << "\n";
			// }
			int b = e.b,d = e.d;
			if(dist[b][d%2] > d || adj[b].size() == 0)
				ans[e.i] = "NIE";
			else 
				ans[e.i] = "TAK";
		}
	}
	for(int i = 0;i<k;i++)
		cout << ans[i] << "\n";
}

Compilation message

mor.cpp: In function 'void setIO(std::string)':
mor.cpp:7:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mor.cpp:8:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 371 ms 52464 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 366 ms 53172 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 460 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 15 ms 416 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 884 KB Output is correct
2 Correct 10 ms 896 KB Output is correct
3 Correct 45 ms 900 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 1476 KB Output is correct
2 Correct 9 ms 588 KB Output is correct
3 Correct 248 ms 1024 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 660 ms 54088 KB Output is correct
2 Correct 16 ms 588 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1402 ms 55660 KB Output is correct
2 Correct 95 ms 11508 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1330 ms 50584 KB Output is correct
2 Correct 206 ms 20736 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1635 ms 50752 KB Output is correct
2 Correct 439 ms 52164 KB Output is correct