Submission #283665

#	Time	Username	Problem	Language	Result	Execution time	Memory
283665		arnold518	Iqea (innopolis2018_final_C)	C++14	36 / 100	2065 ms	118148 KiB

C

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int INF = 5e7;

int N;
pii A[MAXN+10];
vector<int> X[MAXN+10], Y[MAXN+10];

struct Line
{
	int l, r, p;
	Line(int l, int r, int p) : l(l), r(r), p(p) {}
	bool operator < (const Line &q) const { return r<q.r; }
};
int Q;
vector<Line> LX[MAXN+10], LY[MAXN+10];
vector<int> adjX[MAXN+10], adjY[MAXN+10];

pii get(int y, int x)
{
	int nx=lower_bound(LX[y].begin(), LX[y].end(), Line(0, x, 0))->p;
	int ny=lower_bound(LY[x].begin(), LY[x].end(), Line(0, y, 0))->p;
	return {nx, ny};
}

pii P[MAXN+10], T[MAXN+10];
vector<int> VX[MAXN+10], VY[MAXN+10];
unordered_map<ll, int> M2;

struct Tree
{
	int M;
	//vector<vector<int>> adj, cdist;
	//vector<int> sz, del, cpar, cdep;
	int sz[MAXN+10], del[MAXN+10], cpar[MAXN+10], cdist[MAXN+10][30], cdep[MAXN+10];
	vector<int> adj[MAXN+10];

	Tree()
	{
		M=0;
		memset(sz, 0, sizeof(sz));
		memset(del, 0, sizeof(del));
		memset(cpar, 0, sizeof(cpar));
		memset(cdist, 0, sizeof(cdist));
		memset(cdep, 0, sizeof(cdep));
		//sz=del=cpar=cdep=vector<int>(MAXN+10);
		//cdist.resize(MAXN+10);
		//for(auto &it : cdist) it.resize(30);
		//adj.resize(MAXN+10);
	}

	void getsz(int now, int bef)
	{
		sz[now]=1;
		for(int nxt : adj[now])
		{
			if(nxt==bef) continue;
			if(del[nxt]) continue;
			getsz(nxt, now);
			sz[now]+=sz[nxt];
		}
	}

	int getcen(int now, int bef, int S)
	{
		for(int nxt : adj[now])
		{
			if(nxt==bef) continue;
			if(del[nxt]) continue;
			if(sz[nxt]>S/2) return getcen(nxt, now, S);
		}
		return now;
	}

	void dfs(int now, int bef, int t, int dist)
	{
		cdist[now][t]=dist;
		for(int nxt : adj[now])
		{
			if(nxt==bef) continue;
			if(del[nxt]) continue;
			dfs(nxt, now, t, dist+1);
		}
	}

	void decomp(int now, int bef, int cendep)
	{
		getsz(now, now);
		now=getcen(now, now, sz[now]);
		cpar[now]=bef;
		cdep[now]=cendep;

		dfs(now, now, cendep, 0);
		del[now]=true;

		for(auto nxt : adj[now])
		{
			if(del[nxt]) continue;
			decomp(nxt, now, cendep+1);
		}
	}

	void init()
	{
		decomp(1, 0, 1);
		for(int i=1; i<=M; i++) if(!del[i]) while(1);
	}

	vector<int> getpar(int now)
	{
		vector<int> ans;
		while(now)
		{
			ans.push_back(now);
			now=cpar[now];
		}
		return ans;
	}
}TX, TY;

unordered_map<ll, int> M;

int readInt () {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++)
	{
		int y, x;
		//y=readInt(); x=readInt();
		scanf("%d%d", &y, &x);
		A[i]={y, x};
		X[y].push_back(x);
		Y[x].push_back(y);
	}

	for(int i=1; i<=MAXN; i++)
	{
		if(X[i].empty()) continue;
		sort(X[i].begin(), X[i].end());

		int bef=X[i][0];
		for(int j=0; j+1<X[i].size(); j++)
		{
			if(X[i][j]+1<X[i][j+1])
			{
				LX[i].push_back({bef, X[i][j], ++TX.M});
				//printf("LX %d %d %d %d\n", i, LX[i].back().l, LX[i].back().r, LX[i].back().p);
				bef=X[i][j+1];
			}
		}
		LX[i].push_back({bef, X[i].back(), ++TX.M});
		//printf("LX %d %d %d %d\n", i, LX[i].back().l, LX[i].back().r, LX[i].back().p);
	}

	int cnt=0;
	for(int i=2; i<=MAXN; i++)
	{
		if(LX[i].empty() || LX[i-1].empty()) continue;
		int p=0;
		for(auto it : LX[i])
		{
			for(; p<LX[i-1].size() && LX[i-1][p].r<it.l; p++);
			for(; p<LX[i-1].size() && LX[i-1][p].l<=it.r; p++)
			{
				int u=LX[i-1][p].p, v=it.p;
				TX.adj[u].push_back(v);
				TX.adj[v].push_back(u);
				cnt++;
				//printf("adjX %d %d\n", u, v);
			}
			if(p) p--;
		}
	}
	if(cnt!=TX.M-1) while(1);

	for(int i=1; i<=MAXN; i++)
	{
		if(Y[i].empty()) continue;
		sort(Y[i].begin(), Y[i].end());

		int bef=Y[i][0];
		for(int j=0; j+1<Y[i].size(); j++)
		{
			if(Y[i][j]+1!=Y[i][j+1])
			{
				LY[i].push_back({bef, Y[i][j], ++TY.M});
				//printf("LY %d %d %d %d\n", i, LY[i].back().l, LY[i].back().r, LY[i].back().p);
				bef=Y[i][j+1];
			}
		}
		LY[i].push_back({bef, Y[i].back(), ++TY.M});
		//printf("LY %d %d %d %d\n", i, LY[i].back().l, LY[i].back().r, LY[i].back().p);
	}

	cnt=0;
	for(int i=2; i<=MAXN; i++)
	{
		if(LY[i].empty() || LY[i-1].empty()) continue;
		int p=0;
		for(auto it : LY[i])
		{
			for(; p<LY[i-1].size() && LY[i-1][p].r<it.l; p++);
			for(; p<LY[i-1].size() && LY[i-1][p].l<=it.r; p++)
			{
				int u=LY[i-1][p].p, v=it.p;
				TY.adj[u].push_back(v);
				TY.adj[v].push_back(u);
				cnt++;
				//printf("adjY %d %d\n", u, v);
			}
			if(p) p--;
		}
	}
	if(cnt!=TY.M-1) while(1);

	TX.init(); TY.init();

	for(int i=1; i<=N; i++)
	{
		pii t=get(A[i].first, A[i].second);
		VX[i]=TX.getpar(t.first);
		VY[i]=TY.getpar(t.second);
		T[i]=t;

		ll pt=((ll)A[i].first<<20)|A[i].second;
		M2[pt]=i;
	}

	scanf("%d", &Q);
	bool flag=false;
	while(Q--)
	{
		int tt, y, x;
		scanf("%d%d%d", &tt, &y, &x);
		//tt=readInt(); y=readInt(); x=readInt();

		int pt=M2[((ll)y<<20)|x];
		vector<int> &V1=VX[pt], &V2=VY[pt];
		pii &t=T[pt];
		if(tt==1)
		{
			for(auto it : V1) for(auto jt : V2)
			{
				ll pt=((ll)it<<20)|jt;
				if(M.find(pt)==M.end()) M[pt]=INF;
				M[pt]=min(M[pt], TX.cdist[t.first][TX.cdep[it]]+TY.cdist[t.second][TY.cdep[jt]]);
			}
			flag=true;
		}
		else
		{
			if(!flag) { printf("-1\n"); continue; }
			int ans=INF;
			for(auto it : V1) for(auto jt : V2)
			{
				ll pt=((ll)it<<20)|jt;
				if(M.find(pt)==M.end()) continue;
				ans=min(ans, TX.cdist[t.first][TX.cdep[it]]+TY.cdist[t.second][TY.cdep[jt]]+M[pt]);
			}
			if(ans==INF) ans=-1;
			//if(ans!=-1) assert(flag);
			printf("%d\n", ans);
		}
	}
}

Compilation message (stderr)

C.cpp: In function 'int main()':
C.cpp:174:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |   for(int j=0; j+1<X[i].size(); j++)
      |                ~~~^~~~~~~~~~~~
C.cpp:194:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |    for(; p<LX[i-1].size() && LX[i-1][p].r<it.l; p++);
      |          ~^~~~~~~~~~~~~~~
C.cpp:195:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |    for(; p<LX[i-1].size() && LX[i-1][p].l<=it.r; p++)
      |          ~^~~~~~~~~~~~~~~
C.cpp:214:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |   for(int j=0; j+1<Y[i].size(); j++)
      |                ~~~^~~~~~~~~~~~
C.cpp:234:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  234 |    for(; p<LY[i-1].size() && LY[i-1][p].r<it.l; p++);
      |          ~^~~~~~~~~~~~~~~
C.cpp:235:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |    for(; p<LY[i-1].size() && LY[i-1][p].l<=it.r; p++)
      |          ~^~~~~~~~~~~~~~~
C.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
C.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |   scanf("%d%d", &y, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~
C.cpp:261:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  261 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
C.cpp:266:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  266 |   scanf("%d%d%d", &tt, &y, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 29