Submission #82725

#	Time	Username	Problem	Language	Result	Execution time	Memory
82725		farukkastamonuda	Tales of seafaring (POI13_mor)	C++14	100 / 100	2482 ms	43444 KiB

mor

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10