oj.uz

Submission #144518

# Submission time Handle Problem Language Result Execution time Memory
144518 2019-08-17T02:13:34 Z cheetose 물병 (JOI14_bottle) C++11
100 / 100
 2356 ms 147688 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 9876543219876543
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

Pi p[2000][2000];
char s[2000][2001];
Viii edge,e;
int parent[200000];
int find(int a)
{
	if (parent[a] < 0)return a;
	return parent[a] = find(parent[a]);
}
void merge(int a, int b)
{
	a = find(a), b = find(b);
	if (a != b)
	{
		parent[a] += parent[b];
		parent[b] = a;
	}
}
 
int L[200000], R[200000], res[200000];
Pi query[200000];
int main() {
	MEM_1(parent);
	fill(&p[0][0],&p[1999][2000],mp(-1,-1));
	int n,m,N,q;
	scanf("%d%d%d%d",&n,&m,&N,&q);
	fup(i,0,n-1,1)scanf("%s",s[i]);
	queue<Pi> Q;
	fup(i,0,N-1,1)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x--,y--;
		p[x][y]=mp(i,0);
		Q.push(mp(x,y));
	}
	while(!Q.empty())
	{
		int x,y;
		tie(x,y)=Q.front();
		Q.pop();
		int i,d;
		tie(i,d)=p[x][y];
		fup(ii,0,3,1)
		{
			int nx=x+dx[ii],ny=y+dy[ii];
			if(nx>=0 && nx<n && ny>=0 && ny<m && s[nx][ny]=='.')
			{
				if(p[nx][ny].X==-1)
				{
					p[nx][ny]=mp(i,d+1);
					Q.push(mp(nx,ny));
				}
				else
				{
					Pi p1=p[x][y],p2=p[nx][ny];
					if(p1.X<p2.X)edge.pb(iii(p1.Y+p2.Y,p1.X,p2.X));
				}
			}
		}
	}
	sort(ALL(edge));
	int nn=edge.size();
	fup(i,0,nn-1,1)
	{
		int z,x,y;
		tie(z,x,y)=edge[i];
		if(find(x)==find(y))continue;
		e.pb(edge[i]);
	}
	nn=e.size();
	fup(i,0,q-1,1)
	{
		scanf("%d%d",&query[i].X,&query[i].Y);
		query[i].X--,query[i].Y--;
		L[i]=0,R[i]=nn-1;
	}
	vector<Vi> v(nn);
	bool ok = 1;
	while (ok)
	{
		ok = 0;
		MEM_1(parent);
		fup(i, 0, nn - 1, 1)v[i].clear();
		fup(i, 0, q - 1, 1)
		{
			if (L[i] <= R[i])v[(L[i] + R[i]) / 2].push_back(i);
		}
		fup(i, 0, nn - 1, 1)
		{
			merge(get<1>(edge[i]), get<2>(edge[i]));
			while (!v[i].empty())
			{
				ok = 1;
				int t = v[i].back();
				v[i].pop_back();
				if (find(query[t].X) == find(query[t].Y))
				{
					R[t] = i - 1;
					res[t] = get<0>(edge[i]);
				}
				else
					L[t] = i + 1;
			}
		}
	}
	fup(i, 0, q - 1, 1)
	{
		if (L[i] >= nn)puts("-1");
		else printf("%d\n", res[i]);
	}
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&m,&N,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:89:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fup(i,0,n-1,1)scanf("%s",s[i]);
                ~~~~~^~~~~~~~~~~
bottle.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~
bottle.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&query[i].X,&query[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 32888 KB Output is correct
2 Correct 34 ms 33144 KB Output is correct
3 Correct 34 ms 33108 KB Output is correct
4 Correct 173 ms 48140 KB Output is correct
5 Correct 179 ms 48512 KB Output is correct
6 Correct 179 ms 47872 KB Output is correct
7 Correct 173 ms 47812 KB Output is correct
8 Correct 193 ms 50892 KB Output is correct
9 Correct 171 ms 47032 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 37160 KB Output is correct
2 Correct 69 ms 34692 KB Output is correct
3 Correct 240 ms 38716 KB Output is correct
4 Correct 399 ms 44460 KB Output is correct
5 Correct 449 ms 49828 KB Output is correct
6 Correct 245 ms 38224 KB Output is correct
7 Correct 385 ms 43972 KB Output is correct
8 Correct 457 ms 49596 KB Output is correct
9 Correct 532 ms 59800 KB Output is correct
10 Correct 266 ms 42264 KB Output is correct
11 Correct 318 ms 45108 KB Output is correct
12 Correct 168 ms 47144 KB Output is correct
13 Correct 162 ms 41364 KB Output is correct
14 Correct 152 ms 47136 KB Output is correct
15 Correct 159 ms 41384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 37284 KB Output is correct
2 Correct 56 ms 34104 KB Output is correct
3 Correct 219 ms 37932 KB Output is correct
4 Correct 393 ms 44332 KB Output is correct
5 Correct 459 ms 49516 KB Output is correct
6 Correct 604 ms 59648 KB Output is correct
7 Correct 289 ms 43228 KB Output is correct
8 Correct 352 ms 47372 KB Output is correct
9 Correct 183 ms 47404 KB Output is correct
10 Correct 171 ms 42284 KB Output is correct
11 Correct 157 ms 41540 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 56108 KB Output is correct
2 Correct 1180 ms 77752 KB Output is correct
3 Correct 263 ms 42404 KB Output is correct
4 Correct 1851 ms 103088 KB Output is correct
5 Correct 2261 ms 131096 KB Output is correct
6 Correct 766 ms 74276 KB Output is correct
7 Correct 262 ms 42344 KB Output is correct
8 Correct 113 ms 42232 KB Output is correct
9 Correct 2356 ms 147688 KB Output is correct
10 Correct 841 ms 74616 KB Output is correct
11 Correct 1711 ms 118848 KB Output is correct
12 Correct 1151 ms 94960 KB Output is correct