Форум Всеукраїнської інтернет-олімпіади NetOI

int DP[800][800];

main()
 {
    char s[800];
    cin>>s;
    int n=strlen(s);
    DP[0][0]=1;
    
    for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)
    {DP[i][j]=(DP[i][j]+DP[i-1][j])%1000007;
    if(s[i-1]==']' && j)
    DP[i][0]=(DP[i][0]+DP[i-1][j])%1000007;
    if(s[i-1]==')' && j)
    DP[i][j-1]=(DP[i][j-1]+DP[i-1][j])%1000007;
    if(s[i-1]=='(')
    DP[i][j+1]=(DP[i][j+1]+DP[i-1][j])%1000007;}
    
    cout<<DP[n][0]<<endl;
 }

main()
 {
    int n;
    cin>>n;
    if(n%2)
    {cout<<0<<endl;return 0;}
    int S=n*4*5;
    int s=0;
    for(int i=3;i*i<=S;i++)
    if(!(S%i))
    s++;
    cout<<s<<endl;
 }

#define INF 1000000000

struct DSU
{
int *parent;
int *size;

void make_set(int x)
{parent[x]=x;
size[x]=1;}

DSU(int n)
{parent=new int[n];
size=new int[n];
for(int i=0;i<n;i++)
make_set(i);}

DSU(DSU t,int n)
{parent=new int[n];
size=new int[n];
for(int i=0;i<n;i++)
parent[i]=t.parent[i],
size[i]=t.size[i];}

int find_set(int x)
{
    if(parent[x]==x)
    return x;
    else
    return parent[x]=find_set(parent[x]);
}

void union_set(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
    {
        if(size[a]<size[b])
        swap(a,b);
        parent[b]=a;
        size[a]+=size[b];
        
    }
}

};
int n=1000;

int mat[2000][2000];
int G[2000][2000];
int path[2][2000][2000];
bool good[2000*2000];

main()
 {
ios::sync_with_stdio(0);

/*--------- Считывание графа ----------*/
    int a,b;
    cin>>n>>a>>b;
    int sz[n];
    fill(sz,sz+n,0);
    fill(good,good+n*n,1);
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        cin>>mat[i][j];
        if(!mat[i][j])
        mat[i][j]=INF,good[min(i,j)*n+max(i,j)]=0;
        else
        G[i][sz[i]++]=j;
    }
    
    int m;
    cin>>m;
    int bad[m-1];
    int divn[m-1];
    int modn[m-1];
    int x,y;
    cin>>x;
    x--;
    for(int i=1;i<m;i++)
    {
        cin>>y;
        y--;
        bad[i-1]=min(x,y)*n+max(x,y);
        divn[i-1]=min(x,y);
        modn[i-1]=max(x,y);
        good[min(x,y)*n+max(x,y)]=0;
        swap(x,y);
    }
/*-------------------------------------*/
    
    
/*------- Препроцессинг алгоритмом ----*/
/*-------------- Дейкстры -------------*/
    //int path[2][n][n]; // Рёбра, входящие в путь к начальной и конечной вершине от заданной
    int len[2][n]; // Длины кратчайших путей
    int prev[2][n]; // Предыдущие вершины в кратчайших путях
    int ans[2][n]; // Длина кратчайших путей
    bool used[2][n]; // ...
    
    for(int i=0;i<2;i++)
    {
        fill(ans[i],ans[i]+n,INF);
        fill(len[i],len[i]+n,0);
        fill(used[i],used[i]+n,0);
        fill(prev[i],prev[i]+n,-1);
        if(i) ans[i][b-1]=0;
        else ans[i][a-1]=0;
        
        for(int j=0;j<n;j++)
        { // Магия
            int cur=-1;
            for(int k=0;k<n;k++)
                if(!used[i][k] && (cur==-1 || ans[i][k]<ans[i][cur]))
                cur=k;
            
            if(ans[i][cur]==INF)
            break;
            
            used[i][cur]=1;
            
            for(int k=0;k<sz[cur];k++)
            {
                int cc=G[cur][k];
                if(ans[i][cur]+mat[cur][cc]<ans[i][cc])
                {
                    ans[i][cc]=ans[i][cur]+mat[cur][cc];
                    prev[i][cc]=cur;
                }
            }
        }
        
        for(int j=0;j<n;j++)
        { // Восстанавливаем пути и превращаем их, как списки вершин в списки рёбер
            int k=j;
            while(prev[i][k]+1)
            path[i][j][len[i][j]++]=min(prev[i][k],k)*n+max(prev[i][k],k),
            k=prev[i][k];
            sort(path[i][j],path[i][j]+len[i][j]);
        }
    }
/*-------------------------------------*/


/*---------- Подготовка DSU -----------*/
    DSU t(n); 
    for(int j=0;j<n;j++)
    for(int i=0;i<j;i++)
    if(good[i*n+j])
    t.union_set(i,j); // Добавляем все рёбра, кроме "плохих"
/*-------------------------------------*/

/*----------- Поиск ответа ------------*/
    int c_bad;
    
    int c_ans[n]; // Эвристика расстояния до конечной вершины от заданной
    int cost[n]; // Расстояние до начальной вершины от заданной
    
    int i,j;
    
    int c_a,c_b; // Количество вершин, путь в которых из первой 
                 //и из второй вершины соответственно не проходит через запретное ребро
                 
    int c_len; // Длина запрещённого ребра для быстрой замены
    
    int c_num,c_cost,c_h; // Внутри цикла номер текущей вершины, 
                          //длина пути в неё из начала и эвристика длины до конца соответственно
    int c_ok[2][n];
    int mod;
    set<pair<pair<int,int>,int> > que; // Ку!
    for(i=0;i<m-1;i++)
    {
        DSU c(t,n);
        for(j=0;j<m-1;j++) // Быстро (за O(m)) проверяем, будет ли вообще ответ
        if(i!=j)
        c.union_set(divn[j],modn[j]);
        if(c.find_set(a-1)!=c.find_set(b-1))
        {cout<<-1<<' ';continue;}
        
        c_bad=bad[i];
        fill(c_ans,c_ans+n,INF);
        fill(cost,cost,INF);
        
        c_a=0,c_b=0;
        
        for(j=0;j<n;j++) // Считаем, в какую сторону нам предположительно выгоднее искать - к концу или к началу
        c_a+=c_ok[1][j]=!binary_search(path[0][j],path[0][j]+len[0][j],c_bad), // Из данной вершины есть путь в начальную без плохого ребра
        c_b+=c_ok[0][j]=!binary_search(path[1][j],path[1][j]+len[1][j],c_bad); // Из данной вершины есть путь в конечную  без плохого ребра    
        
        c_len=mat[divn[i]][modn[i]]; // Удаляем плохое ребро
        mat[divn[i]][modn[i]]=INF;
        mat[modn[i]][divn[i]]=INF;
        
        if(c_ok[1][b-1])
        {cout<<ans[1][a-1]<<' ';goto PERFECT;}
        if(c_ok[0][a-1])
        {cout<<ans[0][b-1]<<' ';goto PERFECT;}
        
        
        que.clear();
        if(c_a<c_b) 
        mod=0,que.insert(make_pair(make_pair(ans[1][a-1],a-1),0));
        else
        mod=1,que.insert(make_pair(make_pair(ans[0][b-1],b-1),0));
        
        while(!que.empty())
        { 
            c_num=que.begin()->first.second;
            c_h=que.begin()->first.first;
            c_cost=que.begin()->second;
            que.erase(que.begin());
            c_ans[c_num]=c_h;
            cost[c_num]=c_cost;
            
            if(c_ok[mod][c_num])
            {c_ans[mod?a-1:b-1]=c_h;break;}
            for(j=0;j<sz[c_num];j++) 
            {
                int cc=G[c_num][j];
                if(c_ans[cc]>c_cost+mat[c_num][cc]+ans[!mod][cc])
                {
                    que.erase(make_pair(make_pair(c_ans[cc],cc),cost[cc]));
                    c_ans[cc]=c_cost+mat[c_num][cc]+ans[!mod][cc];
                    cost[cc]=c_cost+mat[c_num][cc];
                    que.insert(make_pair(make_pair(c_ans[cc],cc),cost[cc]));
                }
            }
        }
        if(c_a<c_b)
        cout<<c_ans[b-1]<<' ';
        else
        cout<<c_ans[a-1]<<' ';
        
        PERFECT:
        mat[divn[i]][modn[i]]=c_len;
        mat[modn[i]][divn[i]]=c_len;
    }
/*-------------------------------------*/
 }

#define INF 1000000000

struct point
{int x,y;
point(){}
point(int a,int b){x=a,y=b;}
};


main()
{
    ios::sync_with_stdio(0);
// Считывание данных
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int n;
    cin>>n;
    point coords[n+4];
    for(int i=0;i<n;i++)
    cin>>coords[i].x>>coords[i].y;
    coords[n].x=x1;
    coords[n].y=y1;
    coords[n+1].x=x2;
    coords[n+1].y=y2;
    coords[n+2].x=-2000000007;
    coords[n+2].y=-2000000007;
    coords[n+3].x=2000000007;
    coords[n+3].y=2000000007;
    int X[n+4],Y[n+4];
    for(int i=0;i<n+4;i++)
    X[i]=coords[i].x,Y[i]=coords[i].y;
    sort(X,X+n+4);
    sort(Y,Y+n+4);
// Сжатие координат
    map<int,int> new_coord_x,new_coord_y;
    int curx=0,cury=0;
    new_coord_x[X[0]]=0,new_coord_y[Y[0]]=0;
    for(int i=1;i<n+4;i++)
    {
        if(X[i]-X[i-1]==1)
        curx++;
        else if(X[i]-X[i-1]>1)
        curx+=2;
        if(Y[i]-Y[i-1]==1)
        cury++;
        else if(Y[i]-Y[i-1]>1)
        cury+=2;
        
        new_coord_x[X[i]]=curx,
        new_coord_y[Y[i]]=cury;
    }
// Создание карты местности
    int MAP[curx+1][cury+1][4];
    int ans[curx+1][cury+1][4];
    for(int i=0;i<=curx;i++)
    for(int j=0;j<=cury;j++)
    for(int k=0;k<4;k++)
    MAP[i][j][k]=1,
    ans[i][j][k]=INF;
    
    for(int i=0;i<n;i++)
    for(int j=0;j<4;j++)
    MAP[new_coord_x[coords[i].x]][new_coord_y[coords[i].y]][j]=0;
    
    x1=new_coord_x[x1];
    y1=new_coord_y[y1];
    x2=new_coord_x[x2];
    y2=new_coord_y[y2];
    for(int i=0;i<4;i++)
    ans[x1][y1][i]=0,
    MAP[x1][y1][i]=1;
// Поиск в ширину по сжатым координатам
    deque<pair<point,int> > que;
    que.push_back(make_pair(point(x1,y1),4));
    
    int dx[]={1,0,-1,0};
    int dy[]={0,1,0,-1};
    while(!que.empty())
    {
        point cur=que[0].first;
        int x=cur.x;
        int y=cur.y;
        int to=que[0].second;
        que.pop_front();
        if(to!=4)
        {if(!MAP[x][y][to])
        continue;
        MAP[x][y][to]=0;}
        for(int i=0;i<4;i++)
        {
            if(x+dx[i]>=0 && x+dx[i]<=curx && y+dy[i]>=0 && y+dy[i]<=cury && MAP[x+dx[i]][y+dy[i]][i])
            {
                if(i==to)
                {
                    que.push_front(make_pair(point(x+dx[i],y+dy[i]),i));
                    ans[x+dx[i]][y+dy[i]][i]=ans[x][y][i];
                }
                else if(MAP[x+dx[i]][y+dy[i]][i]==1)
                {
                    que.push_back(make_pair(point(x+dx[i],y+dy[i]),i));
                    MAP[x+dx[i]][y+dy[i]][i]=2;
                    if(to==4)
                    ans[x+dx[i]][y+dy[i]][i]=1;
                    else
                    ans[x+dx[i]][y+dy[i]][i]=ans[x][y][to]+1;
                }
            }
        }
    }
    int ANS=*min_element(ans[x2][y2],ans[x2][y2]+4);
    if(ANS==INF)
    cout<<-1<<endl;
    else
    cout<<ANS<<endl;
    
    
}