oj.uz

Submission #82725

# Submission time Handle Problem Language Result Execution time Memory
82725 2018-11-01T13:24:30 Z farukkastamonuda Tales of seafaring (POI13_mor) C++14
100 / 100
 2482 ms 43444 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000009
#define md 1000000007
#define li 5005
#define mp make_pair
#define pb push_back
using namespace std;
int n, m, k, x, y, s, t, d, vis[2][li], dd[2][li];
bool ans[1000005];
vector<int> v[li];
vector< pair<int, pair<int, int> > > quer[li];
queue< pair<int, int> > q;
void solve(int S){
	q.push(mp(0, S));
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i <= 1; i ++){
		for(int j = 1; j <= 5000; j ++){
			dd[i][j] = inf;
		}
	}
	while(!q.empty()){
		pair<int,int> temp = q.front();
		q.pop();
		int seh = temp.se;
		int cst = temp.fi;
		if(vis[cst % 2][ seh ] == 1) continue;
		vis[cst % 2][seh] = 1;
		dd[cst % 2][seh] = cst;
		for(int i = 0;i < (int)v[seh].size(); i ++){
			int go = v[seh][i];
			if(vis[(cst + 1) % 2][go] == 0){
				q.push(mp(cst + 1, go));
			}
		}
	}
	for(int i = 0;i < (int)quer[S].size(); i ++){
		int git = quer[S][i].fi;
		int uzak = quer[S][i].se.fi;
		int ind = quer[S][i].se.se;
		if(vis[uzak % 2][git] == 1 && (int)v[git].size() == 0) continue;
		if(vis[uzak % 2][git] == 1 && dd[uzak % 2][git] <= uzak){
			ans[ind] = 1;
		}
	}
}
int main(){
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i <= m; i ++){
		scanf("%d %d", &x, &y);
		v[x].pb(y);
		v[y].pb(x);
	}
	
	for(int i = 1;i <= k; i ++){
		scanf("%d %d %d", &s, &t, &d);
		quer[s].pb(mp(t, mp(d, i)));
	}
	for(int i = 1; i <= n; i ++){
		solve(i);
	}
	for(int i = 1; i <= k; i ++){
		if(ans[i] == 1) printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}

Compilation message

mor.cpp: In function 'int main()':
mor.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mor.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
mor.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &s, &t, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 2 ms 836 KB Output is correct
4 Correct 478 ms 29924 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 29952 KB Output is correct
2 Correct 7 ms 29952 KB Output is correct
3 Correct 37 ms 29952 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 29952 KB Output is correct
2 Correct 20 ms 29952 KB Output is correct
3 Correct 109 ms 29952 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 29952 KB Output is correct
2 Correct 21 ms 29952 KB Output is correct
3 Correct 566 ms 29952 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1362 ms 31492 KB Output is correct
2 Correct 38 ms 31492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2206 ms 32912 KB Output is correct
2 Correct 129 ms 32912 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2098 ms 32912 KB Output is correct
2 Correct 263 ms 32912 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2482 ms 32912 KB Output is correct
2 Correct 603 ms 43444 KB Output is correct