T14967 交通

题目背景

黄金大神国的首都位于 oier 河中的一座岛屿。一道上班的时候,成千上万辆汽车通过岛屿从西

岸的住宅区(由桥连接岛的西部)到东岸的工业区(由桥连接岛的东部)。

题目描述

黄金大神国的首都位于 oier 河中的一座岛屿。一道上班的时候,成千上万辆汽车通过岛屿从西

岸的住宅区(由桥连接岛的西部)到东岸的工业区(由桥连接岛的东部)。

该岛类似于矩形,它的边平行于主方向。故可将它看作是笛卡尔坐标系中的一个 A*B 的矩形,

它的对角分别为(0, 0)和(A, B)。

岛上有 n 个交通节点(后宫建筑),编号为 1…n,第 i 个节点坐标为(xi, yi)。如果一个节点的坐

标为(0, y),它就位于岛的西岸。类似的,坐标为(A, y)的节点位于岛的东岸。各个节点由街道连接,

每条街道用线段连接两个节点。街道有单向行驶或双向行驶之分。除端点外任意两条街道都没有公

共点。也没有桥梁或者隧道。

你不能对道路网络形状做任何其他假设。沿河岸的街道或节点可能没有入口或者出口街道。由

于交通堵塞日趋严重,黄金大神想快速治理好他的国家,于是聘请你测试岛上当前的道路网是否足

够。要求你写一个程序确定从岛的西岸的每个节点能够到达东岸的多少个节点。

输入输出格式

输入格式:

第 1 行包含 4 个整数 n, m, A, B,分别表示 oier 市中心的节点数,街道数和岛屿的尺寸。

接下来的 n 行,每行包含两个整数 xi,yi (0≤xi≤A,0≤yi≤B),表示第 i 个节点的坐标。任意

两个节点的坐标都不相同。

再往下的 m 行表示街道,每条街道用 3 个整数 ci, di, ki(1≤ci, di≤n, ci≠di, ki∈{1,2}),表示

节点 ci、di 有街道连接,如果 ki=1,表示从 ci 到 di 的街道是单向的,否则,这条街道可以双向行驶。

每个无序对{ci, di}最多出现 1 次。

你可以假设西岸节点中至少有 1 个能够到达东岸的一些节点。

输出格式:

为每个西岸节点输出 1 行,表示这个节点出发能够到达东岸的节点数目

输入输出样例

输入样例#1: 复制

输出样例#1: 复制

说明

对于 30%的数据,n, m≤6000

对于 100%的数据,1≤n≤300000, 0≤m≤900000,1≤A,B≤10^9

一直没有注意一句话,就是题目中有一句,不会有任意两条线段有交点,那么这个图就是平面图,在平面图里面的话,就是说,对于西岸一个点,到达对面东岸的点一定是从西岸所有点能到达的点中连续的一块,所以可以一遍dfs西岸的点,求出能到达的东岸的点,再从这些东岸的点开始跑,看对于西岸的每一个点所能到达最上/最下的东岸的点,然后就可以利用前缀和求出答案。

注意要用bfs,dfs会炸,别问我怎么知道。

现在发现是我的lemon栈开小了。。。

c++代码如下:

 

2 + 5 =