dwangoプログラミングコンテスト

Submission #803104

Source codeソースコード

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

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

int N;
vint lis[26][101010];
char S[101010];

vector<int>G[400];
int match[400];
bool used[400];

void add_edge(int u,int v){
    G[u].pb(v);
    G[v].pb(u);
}

bool dfs(int v){
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
        int u=G[v][i];
        int u_pair=match[u];
        if(u_pair<0||(!used[u_pair]&&dfs(u_pair))){
            match[v]=u;
            match[u]=v;
            return true;
        }
    }
    return false;
}

void init(){
    rep(i,N*2)G[i].clear();
}

int bipartite_matching(){
    int res=0;
    memset(match,-1,sizeof(match));
    for(int v=0;v<N*2;v++){
        if(match[v]<0){
            memset(used,0,sizeof(used));
            if(dfs(v)){
                res++;
            }
        }
    }
    return res;
}



signed main(){
    scanf("%lld",&N);
    for(int i=0;i<N;i++){
        scanf("%s",S);
        for(int j=0;S[j];j++){
            lis[S[j]-'a'][j].pb(i);
        }
    }

    for(int c=0;c<26;c++){
        int cnt=0;
        for(int i=0;i<N-1;i++)if(lis[c][i].size())cnt++;
        for(int i=0;i+N<=101010;i++){
            if(lis[c][i+N-1].size())cnt++;
            if(cnt==N){
                init();
                for(int j=0;j<N;j++){
                    for(int k=0;k<lis[c][i+j].size();k++){
                        add_edge(j,lis[c][i+j][k]+N);
                    }
                }
                if(bipartite_matching()==N){
                    cout<<"YES"<<endl;
                    return 0;
                }
            }
            if(lis[c][i].size())cnt--;
        }
    }
    cout<<"NO"<<endl;
    return 0;
}

Submission

Task問題 B - コメント
User nameユーザ名 latte0119
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 90
Source lengthソースコード長 2224 Byte
File nameファイル名
Exec time実行時間 1357 ms
Memory usageメモリ使用量 65704 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&N);
^
./Main.cpp:68:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",S);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt
Subtask1 30 / 30 sample_01.txt,sample_02.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt
Subtask2 60 / 60 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt,subtask2_13.txt,subtask2_14.txt,subtask2_15.txt,subtask2_16.txt,subtask2_17.txt,subtask2_18.txt,subtask2_19.txt,subtask2_20.txt,subtask2_21.txt,subtask2_22.txt,subtask2_23.txt,subtask2_24.txt,subtask2_25.txt,subtask2_26.txt,subtask2_27.txt,subtask2_28.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 154 ms 62420 KB
sample_02.txt AC 164 ms 62504 KB
subtask1_01.txt AC 163 ms 62504 KB
subtask1_02.txt AC 165 ms 62512 KB
subtask1_03.txt AC 153 ms 62500 KB
subtask1_04.txt AC 155 ms 62444 KB
subtask1_05.txt AC 184 ms 62504 KB
subtask1_06.txt AC 161 ms 62508 KB
subtask1_07.txt AC 146 ms 62504 KB
subtask1_08.txt AC 179 ms 62552 KB
subtask1_09.txt AC 139 ms 62532 KB
subtask1_10.txt AC 168 ms 62476 KB
subtask1_11.txt AC 154 ms 62504 KB
subtask1_12.txt AC 153 ms 62508 KB
subtask1_13.txt AC 144 ms 62500 KB
subtask1_14.txt AC 153 ms 62512 KB
subtask1_15.txt AC 145 ms 62508 KB
subtask1_16.txt AC 153 ms 62504 KB
subtask2_01.txt AC 159 ms 64044 KB
subtask2_02.txt AC 169 ms 64036 KB
subtask2_03.txt AC 149 ms 63652 KB
subtask2_04.txt AC 159 ms 63408 KB
subtask2_05.txt AC 146 ms 63656 KB
subtask2_06.txt AC 1357 ms 65704 KB
subtask2_07.txt AC 152 ms 65704 KB
subtask2_08.txt AC 157 ms 64088 KB
subtask2_09.txt AC 168 ms 64036 KB
subtask2_10.txt AC 153 ms 63016 KB
subtask2_11.txt AC 172 ms 64040 KB
subtask2_12.txt AC 172 ms 64036 KB
subtask2_13.txt AC 165 ms 64048 KB
subtask2_14.txt AC 178 ms 64044 KB
subtask2_15.txt AC 171 ms 64080 KB
subtask2_16.txt AC 183 ms 64164 KB
subtask2_17.txt AC 176 ms 64292 KB
subtask2_18.txt AC 172 ms 64176 KB
subtask2_19.txt AC 172 ms 64172 KB
subtask2_20.txt AC 512 ms 63912 KB
subtask2_21.txt AC 490 ms 63916 KB
subtask2_22.txt AC 503 ms 63920 KB
subtask2_23.txt AC 337 ms 63920 KB
subtask2_24.txt AC 620 ms 64048 KB
subtask2_25.txt AC 487 ms 63916 KB
subtask2_26.txt AC 156 ms 63920 KB
subtask2_27.txt AC 166 ms 63912 KB
subtask2_28.txt AC 167 ms 63916 KB