Submission #283628

#	Time	Username	Problem	Language	Result	Execution time	Memory
283628		arnold518	Iqea (innopolis2018_final_C)	C++14	36 / 100	1714 ms	262148 KiB

C

#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];

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];

	Tree()
	{
		M=0;
		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]/2);
		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++) assert(del[i]);
	}

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

vector<pii> TP1;
vector<int> TP2;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++)
	{
		int y, x;
		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++)
	{
		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--;
		}
	}
	assert(cnt==TX.M-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++)
	{
		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--;
		}
	}
	assert(cnt==TY.M-1);

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

	for(int i=1; i<=N; i++)
	{
		P[i]=get(A[i].first, A[i].second);
		vector<int> V1=TX.getpar(P[i].first);
		vector<int> V2=TY.getpar(P[i].second);
		for(auto it : V1) for(auto jt : V2) TP1.push_back({it, jt});
	}
	sort(TP1.begin(), TP1.end());
	TP1.erase(unique(TP1.begin(), TP1.end()), TP1.end());
	TP2=vector<int>(TP1.size(), INF);

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

		pii t=get(y, x);

		vector<int> V1=TX.getpar(t.first);
		vector<int> V2=TY.getpar(t.second);

		if(tt==1)
		{
			for(auto it : V1) for(auto jt : V2)
			{
				int pt=lower_bound(TP1.begin(), TP1.end(), pii(it, jt))-TP1.begin();
				TP2[pt]=min(TP2[pt], TX.cdist[t.first][TX.cdep[it]]+TY.cdist[t.second][TY.cdep[jt]]);
			}
			flag=true;
		}
		else
		{
			int ans=INF;
			for(auto it : V1) for(auto jt : V2)
			{
				int pt=lower_bound(TP1.begin(), TP1.end(), pii(it, jt))-TP1.begin();
				ans=min(ans, TX.cdist[t.first][TX.cdep[it]]+TY.cdist[t.second][TY.cdep[jt]]+TP2[pt]);
			}
			if(ans==INF) ans=-1;
			if(ans==-1) assert(!flag);
			else assert(flag);
			printf("%d\n", ans);
		}
	}
}

Compilation message (stderr)

C.cpp: In function 'int main()':
C.cpp:140:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |   for(int j=0; j+1<X[i].size(); j++)
      |                ~~~^~~~~~~~~~~~
C.cpp:159:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |    for(; p<LX[i-1].size() && LX[i-1][p].r<it.l; p++);
      |          ~^~~~~~~~~~~~~~~
C.cpp:160:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |    for(; p<LX[i-1].size() && LX[i-1][p].l<=it.r; p++)
      |          ~^~~~~~~~~~~~~~~
C.cpp:179:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |   for(int j=0; j+1<Y[i].size(); j++)
      |                ~~~^~~~~~~~~~~~
C.cpp:198:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |    for(; p<LY[i-1].size() && LY[i-1][p].r<it.l; p++);
      |          ~^~~~~~~~~~~~~~~
C.cpp:199:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |    for(; p<LY[i-1].size() && LY[i-1][p].l<=it.r; p++)
      |          ~^~~~~~~~~~~~~~~
C.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
C.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |   scanf("%d%d", &y, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~
C.cpp:225:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  225 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
C.cpp:230:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  230 |   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