読者です 読者をやめる 読者になる 読者になる

AOJ-ICPC-favorite

好みが普通すぎて面白く無いかもしれません
現在の難易度でsortします

・500

2333 My friends are small
My friends are small | Aizu Online Judge

・600

2439 Hakone
Hakone | Aizu Online Judge

2336 Spring Tiles
Spring Tiles | Aizu Online Judge

2256 Divide the Cake
Divide the Cake | Aizu Online Judge

・650

1333 Beautiful Spacing
Beautiful Spacing | Aizu Online Judge

2374 RabbitLunch
RabbitLunch | Aizu Online Judge

2376 DisconnectedGame
DisconnectedGame | Aizu Online Judge

・700

1322 ASCII Expression
ASCII Expression | Aizu Online Judge

・750

1197 A Die Maker
A Die Maker | Aizu Online Judge
サイコロが面倒要素以外で活用されているのを初めて見た

1343 Hidden Tree
Hidden Tree | Aizu Online Judge

2445 MinimumCostPath
MinimumCostPath | Aizu Online Judge

・900

1353 Sweet War
Sweet War | Aizu Online Judge

・1000

2291 Brilliant Stars
Brilliant Stars | Aizu Online Judge

2337 Remodeling Plan for Neko-Nabe (tentative)
Remodeling Plan for Neko-Nabe (tentative) | Aizu Online Judge

2617 Air Pollution
Air Pollution | Aizu Online Judge

・1100

1185 Patisserie ACM
Patisserie ACM | Aizu Online Judge

2453 Presentation
Presentation | Aizu Online Judge

2339 問題文担当者は働かない!
Person responsible for problem description don't w | Aizu Online Judge

AOJ2453 Presentation

問題:
Presentation | Aizu Online Judge

概要:
二分木をコピペして作る
























解法:
面白かったけど構文解析パート必要ない。あと配列サイズ難しい。

重要なのは,
切り貼りすると1番深いところの深さが元のやつより増加するので,最終的に1番深いところ(どれでもいい)に注目すると,それを含んで貼り付けたやつは部分木丸ごとであること(日本語難しい)
v以下の部分木を貼り付けて作れる必要条件にsz[v] | sz[root] (葉は含めない)があり,また1番深いところから根までに候補がO(N)通りありsz[root]の約数なのでO(sqrt(N))個
これらについてそれぞれO(N)かけて最終的な木が作れるかチェックする ここまで(O(Nsqrt(N)))
また調べる過程でそれぞれの候補について,それより下を使ってそれ自体が作れるかを調べ直す必要はない(最終的に1番深いやつはコピペする前でも1番深いところにあったりいい感じになってる)
あとは普通のdp(二重だけどO(N))

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define MX 400010

struct node{
    int sz;
    bool lf;
    node *p,*l,*r;
    node():sz(1),lf(0),p(NULL),l(NULL),r(NULL){}
};

node pool[MX];
int now;

inline node *get(){return &pool[now++];}

int ma;
node *st;

node *read(const string& s,node *par,int& p,int d){
    node *v=get();
    if(par)v->p=par;
    if(s[p+1]==')'){
	v->sz=0,v->lf=1;
	p+=2;
	if(ma<d)ma=d,st=v;
	return v;
    }
    ++p;
    v->l=read(s,v,p,d+1);
    v->r=read(s,v,p,d+1);
    ++p;
    v->sz+=v->l->sz+v->r->sz;
    return v;
}

bool ok(node* v,node* v2,node* gen){
    if(v->lf)return v2->lf;
    node *lc=v2->l,*rc=v2->r;
    if(v2->lf)lc=gen->l,rc=gen->r;
    return ok(v->l,lc,gen) && ok(v->r,rc,gen);
}

int sz,k;
char in[MX];
string s;
node *root;
vector<node*> sub;
vector<int> vec,dp;

main(){
    scanf("%s",in);
    s=in;
    root=read(s,NULL,k,0);
    sz=root->sz;
    while(st->p){
	if(sz%st->p->sz==0)
	    sub.pb(st->p);
	st=st->p;
    }
    for(auto &v:sub)if(ok(root,v,v))
	vec.pb(v->sz);
    dp.resize(vec.size(),200000);
    dp[0]=0;
    rep(i,vec.size())rep(j,i)
	if(vec[i]%vec[j]==0)
	    dp[i]=min(dp[i],dp[j]+vec[i]/vec[j]-1);
    printf("%d\n",dp.back());
}

AOJ2338 よくわかる二重魔法

問題:
Intelligible Double Magic | Aizu Online Judge

要約すると、N頂点M辺の無向グラフが与えられるので好きに辺を有向にして(u,v)...uからvにいける ような組を多くせよ、という問題(N<=100,M<=N_C_2)





lowlinkを使って二重辺連結成分分解し重みつき木にしてdpすれば求めることができる
DEGwerが言っていたので考えてみたけど、ループの中身を見るとよくある木dp(O(n^3)と思いきやO(n^2)だった系の要素
(参考:二乗の木 DP - (iwi) { 反省します - TopCoder部)
があるのでO(n^4)->O(n^3)な気がする。違うかも。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)

int n,m;
int szt[110],cmp[110],sz[110];
map<string,int> T;
vector<int> g[110],g2[110];
pii es[5010];
int now,ret;
int vis[110],ord[110],low[110],br[110][110];

void dfs(int v,int p){
    vis[v]=1;
    ord[v]=low[v]=now++;
    for(int &to:g[v])if(to!=p){
	if(!vis[to]){
	    dfs(to,v);
	    low[v]=min(low[v],low[to]);
	    if(ord[v]<low[to])br[v][to]=br[to][v]=1;
	}else low[v]=min(low[v],ord[to]);
    }
}

void dfs2(int v){
    vis[v]=szt[v]=1;
    for(int &to:g[v]){
	if(!vis[to]&&!br[v][to]){
	    dfs2(to);
	    szt[v]+=szt[to];
	}
    }
}

void dfs3(int v,int k){
    sz[now]=k;
    cmp[v]=now;
    vis[v]=1;
    for(int &to:g[v])
	if(!vis[to]&&!br[to][v])
	    dfs3(to,k);
}

int dp[110][110][110],m1[110][110],m2[110][110],wg[110];

void DFS(int v,int p){
    dp[v][sz[v]][sz[v]]=sz[v]*sz[v];
    wg[v]=sz[v];
    for(int &to:g2[v])if(to!=p){
	DFS(to,v);
	for(int i=wg[v];i;--i){
	    for(int j=wg[v];j;--j){
		if(dp[v][i][j]==0)continue;
		for(int k=wg[to];k;--k){
		    int x=m1[to][k];
		    if(x)dp[v][i+k][j]=max(dp[v][i+k][j],dp[v][i][j]+x+j*k);
		    x=m2[to][k];
		    if(x)dp[v][i][j+k]=max(dp[v][i][j+k],dp[v][i][j]+x+i*k);
		}
	    }
	}
	wg[v]+=wg[to];
    }
    rep(i,110)rep(j,110){
	m1[v][i]=max(m1[v][i],dp[v][i][j]);
	m2[v][j]=max(m2[v][j],dp[v][i][j]);
    }
}

main(){
    cin>>n>>m;
    string s;
    rep(i,n)cin>>s,T[s]=i;
    rep(i,m){
	string a,b;
	cin>>a>>b;
	int p=T[a],q=T[b];
	g[p].pb(q);g[q].pb(p);
	es[i]=mp(p,q);
    }
    dfs(0,-1);
    now=0;
    rep(i,n)vis[i]=0;
    rep(i,n)if(!vis[i])dfs2(i);
    rep(i,n)vis[i]=0;
    rep(i,n)if(!vis[i]){
	dfs3(i,szt[i]);
	now++;
    }
    rep(i,m){
	int p=cmp[es[i].first],q=cmp[es[i].second];
	if(p!=q)g2[p].pb(q),g2[q].pb(p);
    }
    DFS(0,-1);
    rep(i,110)rep(j,110)ret=max(ret,dp[0][i][j]);
    cout<<ret<<endl;
}

AOJ2377 ThreeRooks

これで1200+以外は1問以上解いた事になった




概要

X*YのマスにK匹のうさぎがいる。互いに攻撃できないように3個のルークを置く場合の数をmod 10^9+7で求めよ

X,Y<=10^9,K<=10^5



解法

3個同じ所に並んでいる場合

2個並んでいて1個はその範囲にはない

3個が直角に並んでいる場合

を数えると解ける。
1,2個目は普通に求まって, 3個目は気合で平面走査する
平面走査では、区間全体にある値を足す,あるところを0にする,ある範囲の和を求める
が出来ると良いのでよくあるsegment treeを使う(座標圧縮はそんなに面倒でもない)

こういうのはvectorをもらって計算する関数を作っておくと、座標を入れ替えるだけで良くて嬉しみがある

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;++i)

const ll MOD=1000000007;
ll ret,p2,p6;
ll X,Y,K,zan;

inline ll c2(ll x){return x*(x-1)%MOD*p2%MOD;}
inline ll c3(ll x){return x*(x-1)%MOD*(x-2)%MOD*p6%MOD;}
inline void md(ll &x,ll y){x+=y;if(x>=MOD)x-=MOD;}

vector<int> xs;
inline int p(int x){return lower_bound(xs.begin(),xs.end(),x)-xs.begin();}
int sz;
struct segtree{
    vector<ll> dat1, dat2;
    void init(int n_){
	for(sz=1;sz<n_;sz*=2);
	dat1=vector<ll>(sz*2,0);
	dat2=vector<ll>(sz*2,0);  
    }
    void add(int a,int b,ll x,int k=0,int l=0,int r=sz){
	if(b<=l||r<=a)return ;
	if(a<=l&&r<=b)md(dat1[k],x);
	else{
	    md(dat2[k],x*(xs[min(b,r)]-xs[max(a,l)])%MOD);
	    add(a,b,x,k*2+1,l,(l+r)/2);
	    add(a,b,x,k*2+2,(l+r)/2,r);
	}
    }

    ll sum(int a,int b,int k=0,int l=0,int r=sz){
	if(b<=l||r<=a)return 0;
	if(a<=l&&r<=b)return (dat1[k]*(xs[r]-xs[l])+dat2[k])%MOD;
	else{
	    ll res=dat1[k]*(xs[min(b,r)]-xs[max(a,l)]);
	    res+=sum(a,b,k*2+1,l,(l+r)/2);
	    res+=sum(a,b,k*2+2,(l+r)/2,r);
	    return res%MOD;
	}
    }
}seg;

ll calc_23(ll h,ll w,vector<pii>& pt){
    ll s=0,my=h;
    sort(pt.begin(),pt.end());
    for(int i=0;i<pt.size();--my){
	int y=pt[i].fi,j=i;
	while(j<pt.size()&&pt[j].fi==y)++j;
	vector<int> v(j-i);
	for(int k=i;k<j;++k)v[k-i]=pt[k].se;
	md(s,(c3(v[0])+c2(v[0])*(zan-v[0]))%MOD);
	for(int k=1;k<v.size();++k){
	    ll t=v[k]-v[k-1]-1;
	    md(s,c3(t)+c2(t)*(zan-t)%MOD);
	}
	ll t=w-1-v.back();
	md(s,c3(t)+c2(t)*(zan-t)%MOD);
	i=j;
    }
    return (s+(my*c3(w)+(zan-w)*c2(w)%MOD*my))%MOD;
}

ll calc_L(ll h,ll w,vector<pii>& pt){
    sort(pt.begin(),pt.end());
    xs.resize(pt.size()*2);
    rep(i,pt.size()){xs[i*2]=pt[i].se;xs[i*2+1]=pt[i].se+1;}
    xs.pb(0);xs.pb(w);
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    seg.init(xs.size());
    int rr=xs.size()-1;

    ll s=0,la=-1;
    for(int i=0;i<pt.size();){
	int y=pt[i].fi,j=i;
	ll g=seg.sum(0,rr);

	seg.add(0,rr,y-la-1);
	ll ng=seg.sum(0,rr);
	md(s,((w-1)*(g+ng-w)%MOD*(y-la-1)%MOD*p2)%MOD);
	while(j<pt.size()&&pt[j].fi==y)++j;
	vector<int> v(j-i);
	for(int k=i;k<j;++k)v[k-i]=pt[k].se;

	if(v[0]>1)md(s,(v[0]-1)*seg.sum(0,p(v[0]))%MOD);

	for(int k=1;k<v.size();++k){
	    ll t=v[k]-v[k-1]-1;
	    if(t>1)md(s,(t-1)*seg.sum(p(v[k-1]+1),p(v[k]))%MOD);
	}
	ll t=w-1-v.back();
	if(t>1)md(s,(t-1)*seg.sum(p(v.back()+1),rr)%MOD);
	seg.add(0,rr,1);
	for(int k=i;k<j;++k){
	    int l=p(pt[k].se);
	    ll x=seg.sum(l,l+1);
	    seg.add(l,l+1,-x);
	}
	i=j;
	la=y;
    }
    if(la!=h-1){
	ll num=h-1-la,t1=seg.sum(0,rr),t2=(t1+w*(num-1))%MOD;
	md(s,(w-1)*(t1+t2)%MOD*num%MOD*p2%MOD);
    }
    return s;
}

int main(){
    p2=(MOD+1)/2;p6=(MOD+1)/6;
    scanf("%lld%lld%lld",&X,&Y,&K);
    vector<pii> pt(K);
    rep(i,K){
	int x,y;
	scanf("%d%d",&x,&y);
	pt[i]=mp(x,y);
    }
    zan=(X*Y-K)%MOD;
    if(zan<3){puts("0");return 0;}
    ret=c3(zan);
    md(ret,MOD-calc_23(X,Y,pt));
    rep(i,K)swap(pt[i].fi,pt[i].se);
    md(ret,MOD-calc_23(Y,X,pt));
    rep(i,K)swap(pt[i].fi,pt[i].se);
    ret+=calc_L(X,Y,pt);
    rep(i,K)pt[i].fi=X-1-pt[i].fi;
    ret+=calc_L(X,Y,pt);
    printf("%d\n",ret%MOD);
    return 0;
}

AOJ2603 Time Table

バスをm本走らせてn人拾う時の待ち時間の和の最小値を求める問題






とりあえずバス停の場所を時間からひくといつ出発するとちょうどかがわかるので、それをsortしてTiとおく

まず何も考えずに愚直なdpの式を立てると
dp[i][d] = min{0<=j<=i}(dp[j][d-1] + sum{j+1<=k<=i}(t[i]-t[j]) )となり、変形すると

dp[i][d] = i * t[i] - Si + min{0<=j<=i}(dp[j][d-1]+Sj - j * Ti) (ただしSiはTiの累積和)

となり、iとjがいい感じに分離できる。

  • jが単調減少, Tiが広義単調増加するので蟻本に載っている形のconvex-hull trickを使うことで加速できる
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

int dp[2010][2010];
int s[2010],t[2010];

ll f(int j,int pos,int d){return dp[d][j]+s[j]-j*pos;}

bool ng(int t1,int t2,int t3,int d){
    ll a1=-t1, b1=dp[d][t1]+s[t1];
    ll a2=-t2, b2=dp[d][t2]+s[t2];
    ll a3=-t3, b3=dp[d][t3]+s[t3];
    return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);
}

int p[2010];
int a,n,m;
int l,r;
int deq[2010];

int main(){
    scanf("%d%d%d",&a,&n,&m);
    rep(i,a)scanf("%d",p+i);
    rep(i,n){int y;scanf("%d%d",t+i,&y);t[i]-=p[y-1];}
    sort(t,t+n);

    rep(i,n) rep(j,i) dp[0][i+1]+=t[i]-t[j];    
    rep(i,n) s[i+1]=s[i]+t[i];

    for(int j=1;j<m;++j){
	l=0,r=0;
	for(int i=1;i<=n;++i){
	    while(l+1<r && ng(deq[r-2],deq[r-1],i,j-1)) --r;
	    deq[r++]=i;
	    while(l+1<r && f(deq[l],t[i-1],j-1) >= f(deq[l+1],t[i-1],j-1)) ++l;
	    dp[j][i]=i*t[i-1]-s[i]+f(deq[l],t[i-1],j-1);
	}
    }
    printf("%d\n",dp[m-1][n]);
    return 0;
}

AOJ2445 MinimumCostPath

MinimumCostPath | Aizu Online Judge


まあまあ面白かった

n * n (n<=10^6)のマス目があって左下から右上に最短距離で行く場合の数(障害物は50個まで)

どう見てもスカスカで、殆ど邪魔されずに行けそうだけど左下と右上付近は混雑するかもしれないので、近くだけbfsして後はdp(経路を最初に通る障害物で区別したりするとなんとかなる)

New Year Contest 2015

rng_58さんのコンテスト。まだあんまり解けてないけど面白かった。
とりあえずコンテスト中に通った分だけ

A : 愚直にやればよい(vectorは比較出来るらしい)

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

int n;
vector<int> a,b;

int main(){
    cin>>n;
    while(n){
	a.pb(n&1);
	n/=2;
    }
    b=a;
    reverse(b.begin(),b.end());
    if(a==b) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}

B : sortしてgreedyに拾っていく

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;++i)

int n,ret;
ll a[1010],s;

int main(){
    cin>>n;
    rep(i,n) cin>>a[i];
    a[n]=LLONG_MAX;
    sort(a,a+n);
    s=a[0];ret=1;
    for(int i=1;i<n;){
	int v=upper_bound(a+i,a+n,s)-a;
	if(v==n) break;
	i=v;
	s+=a[v];
	++ret;
    }
    printf("%d\n",ret);

    return 0;
}

C : 一見難しそうだけど、少し考えると、元ある文字と文字の間には、1文字目が異なるならなんでも挿入出来ることがわかる。DPしなくても出来るらしい。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)

bool ok[5010][5010];
string s,t;

bool ch(){
    if(s.size()>t.size()) return 0;
    ok[0][0]=1;
    rep(i,s.size()){
	int mi=5010;
	rep(j,t.size()){
	    if(ok[i][j]&&s[i]==t[j]){
		ok[i+1][j+1]=1;
		if(j+1<t.size()&&t[j]!=t[j+1]){
		    mi=min(mi,j+1);
		}
	    }
	}
	for(int j=mi;j<=t.size();++j) ok[i+1][j]=1;
    }
    return ok[s.size()][t.size()];
}

int main(){
    cin>>s>>t;
    if(ch()) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}

D : 問題文が親切。x -> a*2 - xに移る。更にb*2 - (a*2 - x) = b*2 - a*2 + xという風に、xに関係なく移動幅が決まるので0から偶奇別にBFSするとなんとかなる。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;++i)

const int B = 50010;
int d[2][100050],n,a[210],q;

int main(){
    memset(d,-1,sizeof(d));
    scanf("%d",&n);
    rep(i,n){scanf("%d",a+i);a[i]*=2;}
    queue<pii> que;
    que.push(mp(0,B));
    d[0][B]=0;
    while(!que.empty()){
	pii p=que.front();que.pop();
	int f=p.fi,x=p.se-B;
	rep(i,n){
	    int nx=a[i]-x;
	    if(nx>=-20000&&nx<=30000&&d[f^1][nx+B]==-1){
		d[f^1][nx+B]=d[f][x+B]+1;
		que.push(mp(f^1,nx+B));
	    }
	}
    }
    scanf("%d",&q);
    while(q--){
	int s,t;
	scanf("%d%d",&s,&t);

	int l=d[0][t-s+B],r=d[1][t+s+B],as;
	if(l!=-1&&r!=-1) as=min(l,r);
	else if(l!=-1) as=l;
	else if(r!=-1) as=r;
	else as=-1;
	printf("%d\n",as);
    }
    return 0;
}

G : JOIでよくありそうな感じ。最短路的なことをすると解けるが適当にやると計算量がダメ。
もう動き出して他にぶつかるのを考えた点を消す&同じ向きのロボットに当たったらそっちを動かすことにして打ち切ると大丈夫。

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

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;++i)

int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};

struct ev{
    int id;ll tt;
    ev(int id, ll tt):id(id),tt(tt){}
    bool operator<(const ev& a) const{ return tt>a.tt; }
};

int n;
int dir[100010];
ll t,st[100010];
pii po[100010];
vector<int> xs,ys;
set<pii> sx[100010],sy[100010];

void rem(int i){
    int xx=lower_bound(xs.begin(),xs.end(),po[i].fi)-xs.begin(),
	yy=lower_bound(ys.begin(),ys.end(),po[i].se)-ys.begin();
    sy[xx].erase(mp(po[i].se,i));
    sx[yy].erase(mp(po[i].fi,i));
}

int main(){
    scanf("%d%lld",&n,&t);
    rep(i,n) st[i]=LLONG_MAX;    
    rep(i,n){
	char c[3];
	scanf("%d%d%s",&po[i].fi,&po[i].se,c);
	if(c[0]=='U') dir[i]=0;
	else if(c[0]=='D') dir[i]=1;
	else if(c[0]=='L') dir[i]=2;
	else dir[i]=3;
	xs.pb(po[i].fi); ys.pb(po[i].se);
    }
    sort(xs.begin(),xs.end()); sort(ys.begin(),ys.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end()); ys.erase(unique(ys.begin(),ys.end()),ys.end());

    rep(i,n){
	int xx=lower_bound(xs.begin(),xs.end(),po[i].fi)-xs.begin(),
	    yy=lower_bound(ys.begin(),ys.end(),po[i].se)-ys.begin();
	sx[yy].insert(mp(po[i].fi,i));
	sy[xx].insert(mp(po[i].se,i));
    }

    priority_queue<ev> que;
    que.push(ev(0,0));
    while(!que.empty()){
	ev e=que.top(); que.pop();
	if(st[e.id]<e.tt) continue;
	int xx=lower_bound(xs.begin(),xs.end(),po[e.id].fi)-xs.begin(),
	    yy=lower_bound(ys.begin(),ys.end(),po[e.id].se)-ys.begin();	
	st[e.id]=e.tt;
	rem(e.id);

	int d=dir[e.id];
	if(d==0){
	    for(auto it=sy[xx].upper_bound(mp(po[e.id].se,-1));it!=sy[xx].end();++it){
		int ii=(*it).se;
		ll nt=e.tt+(*it).fi-po[e.id].se;
		que.push(ev(ii,nt));
		if(dir[ii]==d) break;
	    }
	}else if(d==1){
	    for(auto it=sy[xx].lower_bound(mp(po[e.id].se,-1));;){
		if(it==sy[xx].begin()) break;
		--it;
		int ii=(*it).se;
		ll nt=e.tt-(*it).fi+po[e.id].se;
		que.push(ev(ii,nt));
		if(dir[ii]==d) break;
	    }	    
	}else if(d==3){
	    for(auto it=sx[yy].upper_bound(mp(po[e.id].fi,-1));it!=sx[yy].end();++it){
		int ii=(*it).se;
		ll nt=e.tt+(*it).fi-po[e.id].fi;
		que.push(ev(ii,nt));
		if(dir[ii]==d) break;
	    }
	}else{
	    for(auto it=sx[yy].lower_bound(mp(po[e.id].fi,-1));;){
		if(it==sx[yy].begin()) break;
		--it;
		int ii=(*it).se;
		ll nt=e.tt-(*it).fi+po[e.id].fi;
		que.push(ev(ii,nt));
		if(dir[ii]==d) break;
	    }	    
	}
    }
    rep(i,n){
	ll px=po[i].fi,py=po[i].se;
	if(st[i]<=t){
	    px+=(t-st[i])*dx[dir[i]];
	    py+=(t-st[i])*dy[dir[i]];
	}
	printf("%lld %lld\n", px, py);
    }
    return 0;
}