Submission #45642320

---

Source Code Expand

#include<bits/stdc++.h>


#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>

using namespace std; 


namespace atcoder {

	namespace internal {
	
	template <class T> struct simple_queue {
	    std::vector<T> payload;
	    int pos = 0;
	    void reserve(int n) { payload.reserve(n); }
	    int size() const { return int(payload.size()) - pos; }
	    bool empty() const { return pos == int(payload.size()); }
	    void push(const T& t) { payload.push_back(t); }
	    T& front() { return payload[pos]; }
	    void clear() {
	        payload.clear();
	        pos = 0;
	    }
	    void pop() { pos++; }
	};
	
	}  // namespace internal

	template <class Cap> struct mf_graph {
	  public:
	    mf_graph() : _n(0) {}
	    explicit mf_graph(int n) : _n(n), g(n) {}
	
	    int add_edge(int from, int to, Cap cap) {
	        assert(0 <= from && from < _n);
	        assert(0 <= to && to < _n);
	        assert(0 <= cap);
	        int m = int(pos.size());
	        pos.push_back({from, int(g[from].size())});
	        int from_id = int(g[from].size());
	        int to_id = int(g[to].size());
	        if (from == to) to_id++;
	        g[from].push_back(_edge{to, to_id, cap});
	        g[to].push_back(_edge{from, from_id, 0});
	        return m;
	    }
	
	    struct edge {
	        int from, to;
	        Cap cap, flow;
	    };
	
	    edge get_edge(int i) {
	        int m = int(pos.size());
	        assert(0 <= i && i < m);
	        auto _e = g[pos[i].first][pos[i].second];
	        auto _re = g[_e.to][_e.rev];
	        return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
	    }
	    std::vector<edge> edges() {
	        int m = int(pos.size());
	        std::vector<edge> result;
	        for (int i = 0; i < m; i++) {
	            result.push_back(get_edge(i));
	        }
	        return result;
	    }
	    void change_edge(int i, Cap new_cap, Cap new_flow) {
	        int m = int(pos.size());
	        assert(0 <= i && i < m);
	        assert(0 <= new_flow && new_flow <= new_cap);
	        auto& _e = g[pos[i].first][pos[i].second];
	        auto& _re = g[_e.to][_e.rev];
	        _e.cap = new_cap - new_flow;
	        _re.cap = new_flow;
	    }
	
	    Cap flow(int s, int t) {
	        return flow(s, t, std::numeric_limits<Cap>::max());
	    }
	    Cap flow(int s, int t, Cap flow_limit) {
	        assert(0 <= s && s < _n);
	        assert(0 <= t && t < _n);
	        assert(s != t);
	
	        std::vector<int> level(_n), iter(_n);
	        internal::simple_queue<int> que;
	
	        auto bfs = [&]() {
	            std::fill(level.begin(), level.end(), -1);
	            level[s] = 0;
	            que.clear();
	            que.push(s);
	            while (!que.empty()) {
	                int v = que.front();
	                que.pop();
	                for (auto e : g[v]) {
	                    if (e.cap == 0 || level[e.to] >= 0) continue;
	                    level[e.to] = level[v] + 1;
	                    if (e.to == t) return;
	                    que.push(e.to);
	                }
	            }
	        };
	        auto dfs = [&](auto self, int v, Cap up) {
	            if (v == s) return up;
	            Cap res = 0;
	            int level_v = level[v];
	            for (int& i = iter[v]; i < int(g[v].size()); i++) {
	                _edge& e = g[v][i];
	                if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
	                Cap d =
	                    self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
	                if (d <= 0) continue;
	                g[v][i].cap += d;
	                g[e.to][e.rev].cap -= d;
	                res += d;
	                if (res == up) return res;
	            }
	            level[v] = _n;
	            return res;
	        };
	
	        Cap flow = 0;
	        while (flow < flow_limit) {
	            bfs();
	            if (level[t] == -1) break;
	            std::fill(iter.begin(), iter.end(), 0);
	            Cap f = dfs(dfs, t, flow_limit - flow);
	            if (!f) break;
	            flow += f;
	        }
	        return flow;
	    }
	
	    std::vector<bool> min_cut(int s) {
	        std::vector<bool> visited(_n);
	        internal::simple_queue<int> que;
	        que.push(s);
	        while (!que.empty()) {
	            int p = que.front();
	            que.pop();
	            visited[p] = true;
	            for (auto e : g[p]) {
	                if (e.cap && !visited[e.to]) {
	                    visited[e.to] = true;
	                    que.push(e.to);
	                }
	            }
	        }
	        return visited;
	    }
	
	  private:
	    int _n;
	    struct _edge {
	        int to, rev;
	        Cap cap;
	    };
	    std::vector<std::pair<int, int>> pos;
	    std::vector<std::vector<_edge>> g;
	};

}  // namespace atcoder

using namespace atcoder;

inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define M 200010
//#define mo
#define N 510
int n, m, i, j, k, T, ans=2e9;
char s[M]; 
int le[N][11], l, r, mid, c, tot; 
vector<int>v[N][11]; 
map<int, int>mp; 

int check(int T) {
//	printf(">> %d %d\n", T, c); 
	mf_graph<int>G(N*N); mp.clear(); tot=n; 
//		printf(">> %d %d\n", T, c); 

	for(i=1; i<=n; ++i) G.add_edge(N*N-2, i, 1); 
	for(i=1; i<=n; ++i) {
		for(j=0, k=0; j<=n; ++j) {
			k=v[i][c][j%le[i][c]]+m*(j/le[i][c]); 
			if(k>T) break; 
			if(!mp[k+n]) 
				mp[k+n]=++tot, G.add_edge(tot, N*N-1, 1); 
//			if(c==7) printf("%d %d %d (%d %d %d)\n", i, k+n, mp[k+n], j, j%le[i][c], j/le[i][c]); 
			G.add_edge(i, mp[k+n], 1); 
		}
	}
//	printf("hi\n"); 
	if(G.flow(N*N-2, N*N-1, n)==n) return 1; 
	return 0; 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	for(i=1; i<=n; ++i) {
		scanf("%s", s); 
		for(j=0; s[j]; ++j) v[i][s[j]-'0'].pb(j); 
	}
	for(c=0; c<=9; ++c) for(i=1; i<=n; ++i) 
		le[i][c]=v[i][c].size(); 
	for(c=0; c<=9; ++c) {
		for(i=1; i<=n; ++i) if(!le[i][c]) break; 
		if(i<=n) continue; 
		l=n-1; r=1e9; 
		while(l<r) {
			mid=(l+r)>>1; 
//			printf("[%d %d]\n", l, r); 
			if(check(mid)) r=mid; 
			else l=mid+1; 
		}
		ans=min(ans, l); 
//		printf("---%d %d\n", c, ans); 
	}
	if(ans==2e9) printf("-1"); 
	else printf("%d", ans); 
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:220:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  220 |                 scanf("%s", s);
      |                 ~~~~~^~~~~~~~~

Judge Result