Submission #1013380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013380		vjudge1	Tales of seafaring (POI13_mor)	C++17	50 / 100	230 ms	41244 KiB

mor

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
namespace debug { template <class c> struct rge { c b, e; }; template <class c> rge<c> range(c i, c j) { return rge<c>{i, j}; } template <class c> char spk(...); template <class c> auto spk(c* a) -> decltype(cerr << *a, 0); struct stream { ~stream() { cerr << endl; } template <class c> typename enable_if <sizeof spk<c>(0) != 1, stream&>::type operator<<(c i) { cerr << boolalpha << i; return *this; } template <class c> typename enable_if <sizeof spk<c>(0) == 1, stream&>::type operator<<(c i) { return *this << range(begin(i), end(i)); } template <class a, class b> stream& operator<<(pair <a,b> p) { return *this << "(" << p.first << ", " << p.second << ")"; } template <class c> stream& operator<<(rge<c> d) { *this << "["; for (auto it=d.b; it!=d.e; it++) *this << ", " + 2 * (it == d.b) << *it; return *this << "]"; } stream& _dbg(const string& s, int i, int b) { return *this; } template <class c, class ... cs> stream& _dbg(const string& s, int i, int b, c arg, cs ... args) { if (i == (int)(s.size())) return (*this << ": " << arg); b += (s[i] == '(') + (s[i] == '[') + (s[i] == '{') - (s[i] == ')') - (s[i] == ']') - (s[i] == '}'); return (s[i] == ',' && b == 0) ? (*this << ": " << arg << "     ")._dbg(s, i + 1, b, args...) : (s[i] == ' ' ? *this : *this << s[i])._dbg(s, i + 1, b, arg, args...); } };}
#define dout debug::stream()
#define dbg(...) ((dout << ">> ")._dbg(#__VA_ARGS__, 0, 0, __VA_ARGS__))
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define ss(x) ((int)((x).size()))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(b);i>=(a);i--)
#define upgrade cin.tie(0)->sync_with_stdio(0);
template <class p, class q> pair<p,q> operator-(pair<p,q> a, pair<p,q> b) { return mp(a.f - b.f, a.s - b.s); }
template <class p, class q> pair<p,q> operator+(pair<p,q> a, pair<p,q> b) { return mp(a.f + b.f, a.s + b.s); }
template <class p, class q> void umin(p &a, const q &b) { if (a > b) a = b; }
template <class p, class q> void umax(p &a, const q &b) { if (a < b) a = b; }
using lf = long double;
using ll = long long;
using cll = const ll;
using cint = const int;

const int inf = 1e9 + 5;
const int N = 5005;
const int Q = 1e6 + 5;
int n, m, q;
int res[Q];
int dis[N][2];
vector <int> e[N];
vector < tuple <int, int, int> > queries[N];

void solve(int s)
{
	if (e[s].empty()) return;
	
	rep(u, 1, n) dis[u][0] = dis[u][1] = inf;
	
	dis[s][0] = 0;
	
	queue < pair <int, int> > Q;
	
	Q.push({s, 0});

	while (!Q.empty()){
		auto[u, p] = Q.front();
		Q.pop();
		for (int v : e[u]){
			if (dis[v][p ^ 1] > dis[u][p] + 1){
				dis[v][p ^ 1] = dis[u][p] + 1;
				Q.push({v, p ^ 1});
			}
		}
	}

	for (auto[t, d, i] : queries[s]){
		if (dis[t][d % 2] <= d){
			res[i] = true;
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &q);

	assert(n <= 800);

	while (m--){
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].pb(v);
		e[v].pb(u);
	}

	rep(i, 1, q){
		int s, t, d;
		scanf("%d%d%d", &s, &t, &d);
		queries[s].pb({t, d, i});
	}

	rep(i, 1, n) solve(i);

	rep(i, 1, q) printf("%s\n", res[i] ? "TAK" : "NIE");
}

Compilation message (stderr)

mor.cpp: In function 'int main()':
mor.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mor.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
mor.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   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: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10