제출 #154400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154400		davitmarg	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	49 / 100	288 ms	71256 KiB

garden

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin (),v.end()
using namespace std;

#ifndef death
    #include "garden.h"
    #include "gardenlib.h"
#endif

#ifdef death
    void answer(int x)
    {
        cout<<"! "<<x<<endl;
    }
#endif

int n,m,p,q,c[2003],used[150005];
LL dp[150005][32];
int dir[2*150005],nxt[2*150005][32];
vector<pair<int,int>> g[150005];
void addNode(int a,int b)
{
    dir[a]=b;
    //cout<<a<<" "<<b<<endl;
}

void count_routes(int N,int M,int P,int R[][2] ,int Q,int K[])
{
    n=N;
    m=M;
    q=Q;
    p=P+1;
    for(int i=0;i<m;i++)
    {
        int a=R[i][0]+1,b=R[i][1]+1;
        g[a].PB(MP(i,b));
        g[b].PB(MP(i,a));
    }
    for(int i=1;i<=q;i++)
        c[i]=K[i-1];
    
    for(int i=1;i<=n;i++)
        sort(all(g[i]));

    for(int i=1;i<=n;i++)
    {
        int to;

        if(g[i].empty())
            continue;

        to=g[i][0].second;
        if(i==g[to][0].second)
            addNode(i,n+to);
        else    
            addNode(i,to);

        if(g[i].size()==1)
            to=g[i][0].second; 
        else
            to=g[i][1].second;

        if(i==g[to][0].second)
            addNode(i+n,to+n);
        else
            addNode(i+n,to);
    }
    for(int i=1;i<=2*n;i++)
        nxt[i][0]=dir[i];

    for(int j=1;j<29;j++)
        for(int i=1;i<=2*n;i++)
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
            
    for(int k=1;k<=q;k++)
    {
        int K=c[k];
        vector<int> s;
        for(int j=0;j<=29;j++)
        {
            if(K%2)
                s.PB(j);
            K/=2;
        }
        for(int i=1;i<=2*n;i++)
            for(int j=0;j<=29;j++)
                dp[i][j]=0;
        for(int i=1;i<=n;i++)
            dp[nxt[i][s[0]]][0]++;
        
        for(int j=1;j<s.size();j++)
            for(int i=1;i<=2*n;i++)
                dp[ nxt[i][s[j]] ][j]+=dp[i][j-1];
        answer(dp[p][s.size()-1]+dp[p+n][s.size()-1]);
    }
    
}



#ifdef death

int main()
{
    int N,M,Q,P,R[102][2],K[102];
    cin>>N>>M>>P;
    for(int i=0;i<M;i++)
        cin>>R[i][0]>>R[i][1];
    cin>>Q;
    for(int i=0;i<Q;i++)
        cin>>K[i];
    count_routes(N,M,P,R,Q,K);
	return 0;
}

#endif
 
/*


2 1 0
0 1
1
1
 
*/

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<s.size();j++)
                     ~^~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31