ACAC001

AOJのArchived Classic Algorithm Contest 001というコンテストが今日あったようです。
僕は出なかったのですが、問題を見て解いてみると1つもWAを出すことなく全完できました（めっちゃうれしい）やたら嬉しいのでソース載せます。

A

繰り返し2乗法。やるだけ。

ソースコード

#include <iostream>
using namespace std;
typedef long long ll;
#define MOD 1000000007
ll pow(ll a,ll x)
{
    ll res=1ll;
    while(x)
    {
        if(x&1)res=res*a%MOD;
        a=a*a%MOD;
        x>>=1;
    }
    return res;
}
int main()
{
    ll a,x;
    cin >> a >> x;
    cout << pow(a,x) << endl;
    return 0;
}

B

直線の交点の座標を頑張って求める。手元で計算してそのまま実装しました。傾き∞の場合に注意。汚くてごめんなさいm(__)m

ソースコード

#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
     
    int q;
    cin >> q;
    double x[4],y[4];
    for(int i=0;i<q;i++)
    {
        for(int i=0;i<4;i++)
        {
            cin >> x[i] >> y[i];
        }
        if(x[1]==x[0])
        {
            cout << setprecision(16) << x[0] << ' ' << (y[3]-y[2])/(x[3]-x[2])*(x[0]-x[2])+y[2] << endl;
            continue;
        }
        if(x[2]==x[3])
        {
            cout << setprecision(16) << x[2] << ' ' << (y[1]-y[0])/(x[1]-x[0])*(x[2]-x[0])+y[0] << endl;
            continue;
        }
        double xp=(x[2]*(y[2]-y[3])/(x[3]-x[2])+x[0]*(y[1]-y[0])/(x[1]-x[0])+y[2]-y[0])/((y[1]-y[0])/(x[1]-x[0])-(y[3]-y[2])/(x[3]-x[2]));
        cout << setprecision(16) << xp << ' ' << (y[1]-y[0])/(x[1]-x[0])*(xp-x[0])+y[0] << endl;
    }
    return 0;
}

C

RMQ。segtreeを頑張って書く。

ソースコード

#include <iostream>
#include <algorithm>
using namespace std;
#define SIZE (1<<18)-1
int seg[SIZE];
int n,q;
void init()
{
    fill(seg,seg+SIZE,(1<<31)-1);
    cin >> n >> q;
    return;
}
void update(int k,int x)
{
    k+=(1<<17)-1;
    seg[k]=x;
    while(k)
    {
        k=(k-1)/2;
        seg[k]=min(seg[k*2+1],seg[k*2+2]);
    }
    return;
}
int query(int a,int b,int k,int l,int r)
{
    if(r<=a||b<=l)return (1<<31)-1;
    if(a<=l&&r<=b)return seg[k];
    return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
}
int main()
{
    init();
    for(int i=0;i<q;i++)
    {
        int type,x,y;
        cin >> type >> x >> y;
        if(type==0)update(x,y);
        if(type==1)cout << query(x,y+1,0,0,1<<17) << endl;
    }
    return 0;
}

D

強連結成分分解をする。問題文が直接的すぎる(^_^;)
僕は強連結成分分解が好きなので何回も復習しているうちに蟻本の実装が頭に染み付きました。
他にLCAとかも好きです（笑）

ソースコード

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
vector<int> G[10010],rG[10010];
vector<int> vs;
int V,E,Q;
bool used[10010];
int cmp[10010];
void add_edge(int from,int to)
{
    G[from].pb(to);
    rG[to].pb(from);
    return;
}
void dfs(int s)
{
    used[s]=true;
    for(int i=0;i<G[s].size();i++)
    {
        if(!used[G[s][i]])dfs(G[s][i]);
    }
    vs.pb(s);
}
void rdfs(int s,int k)
{
    used[s]=true;
    cmp[s]=k;
    for(int i=0;i<rG[s].size();i++)
    {
        if(!used[rG[s][i]])rdfs(rG[s][i],k);
    }
}
int scc()
{
    memset(used,0,sizeof(used));
    vs.clear();
    for(int v=0;v<V;v++)
    {
        if(!used[v])dfs(v);
    }
    memset(used,0,sizeof(used));
    int k=0;
    for(int i=vs.size()-1;i>=0;i--)
    {
        if(!used[vs[i]])rdfs(vs[i],k++);
    }
    return k;
}
int same(int u,int v)
{
    if(cmp[u]==cmp[v])return 1;
    else return 0;
}
int main()
{
    cin >> V >> E;
    for(int i=0;i<E;i++)
    {
        int s,t;
        cin >> s >> t;
        add_edge(s,t);
    }
    scc();
    cin >> Q;
    for(int i=0;i<Q;i++)
    {
        int u,v;
        cin >> u >> v;
        cout << same(u,v) << endl;
    }
    return 0;
}