# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
45326 | 2018-04-12T21:48:31 Z | imaxblue | Tales of seafaring (POI13_mor) | C++17 | 2645 ms | 65536 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define x first #define y second #define pii pair<int, int> #define p3i pair<pii, int> #define pll pair<ll, ll> #define p3l pair<pll, ll> #define vi vector<int> #define vpii vector<pii> #define vp3i vector<p3i> #define vpll vector<pll> #define vp3l vector<p3l> #define lseg L, (L+R)/2, N*2+1 #define rseg (L+R)/2+1, R, N*2+2 #define ub upper_bound #define lb lower_bound #define PQ priority_queue #define MN 1000000007 #define fox(k, x) for (int k=0; k<x; ++k) #define fox1(k, x) for (int k=1; k<=x; ++k) #define foxr(k, x) for (int k=x-1; k>=0; --k) #define fox1r(k, x) for (int k=x; k>0; --k) #define ms multiset #define flood(x) memset(x, 0x3f3f3f3f, sizeof x) #define drain(x) memset(x, 0, sizeof x) #define rng() ((rand() << 14)+rand()) #define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0) char _; #define pi 3.14159265358979323846 #define top front int d[2][5005]; int n, m, q, x, y, w, N, D, p; bool T, ans[1000005]; bitset<5005> u[2]; vector<int> v[5005]; vector<p3i> qn[5005]; queue<pair<int, int> > pq; void dijk(int S){ flood(d); drain(u); pq.push(mp(0, S)); while(!pq.empty()){ D=pq.top().x; T=D%2; N=pq.top().y; pq.pop(); if (u[T][N]) continue; d[T][N]=D; u[T][N]=1; fox(l, v[N].size()){ if (!u[!T][v[N][l]]) pq.push(mp(D+1, v[N][l])); } } fox(l, qn[S].size()){ y=qn[S][l].x.x; w=qn[S][l].x.y; p=qn[S][l].y; if (u[w%2][y] && v[y].size()==0) continue; if (u[w%2][y] && d[w%2][y]<=w){ ans[p]=1; } } } int32_t main(){ scanf("%i%i%i", &n, &m, &q); fox(l, m){ scanf("%i%i", &x, &y); v[x].pb(y); v[y].pb(x); } fox(l, q){ scanf("%i%i%i", &x, &y, &w); qn[x].pb(mp(mp(y, w), l)); continue; } fox1(l, n){ dijk(l); } fox(l, q){ printf((ans[l]?"TAK\n":"NIE\n")); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 612 KB | Output is correct |
3 | Correct | 2 ms | 768 KB | Output is correct |
4 | Correct | 466 ms | 38112 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 38112 KB | Output is correct |
2 | Correct | 2 ms | 38112 KB | Output is correct |
3 | Correct | 2 ms | 38112 KB | Output is correct |
4 | Correct | 433 ms | 53860 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 53860 KB | Output is correct |
2 | Correct | 2 ms | 53860 KB | Output is correct |
3 | Correct | 3 ms | 53860 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 53860 KB | Output is correct |
2 | Correct | 5 ms | 53860 KB | Output is correct |
3 | Correct | 44 ms | 53860 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 78 ms | 53860 KB | Output is correct |
2 | Correct | 16 ms | 53860 KB | Output is correct |
3 | Correct | 122 ms | 53860 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 179 ms | 53860 KB | Output is correct |
2 | Correct | 19 ms | 53860 KB | Output is correct |
3 | Correct | 625 ms | 53860 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1268 ms | 55128 KB | Output is correct |
2 | Correct | 28 ms | 55128 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2275 ms | 65536 KB | Output is correct |
2 | Correct | 130 ms | 65536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2300 ms | 65536 KB | Output is correct |
2 | Correct | 255 ms | 65536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2645 ms | 65536 KB | Output is correct |
2 | Correct | 562 ms | 65536 KB | Output is correct |