QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405518#7857. (-1,1)-Sumpletednialh#Compile Error//C++233.6kb2024-05-06 03:22:392024-05-06 03:22:39

Judging History

你现在查看的是最新测评结果

  • [2024-05-06 03:22:39]
  • 评测
  • [2024-05-06 03:22:39]
  • 提交

answer

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

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define sq(a) ((a)*(a))

#define per(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a,b) for (int i=a; i<b; i++)

#define FOR(i,a,b) for (int i=a; i<b; i++)
#define F0R(i,a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
#define R0F(i,a) for (int i = (a)-1; i >= 0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << endl, 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
#define _ << " _ " <<

#define ll int

using vi = vector<int>;
using vvi = vector<vi>;

struct Dinic {
	struct Edge {
		int to, rev;
		ll c, oc;
		ll flow() { return max(oc - c, 0LL); } // if you need flows
	};
	vi lvl, ptr, q;
	vector<vector<Edge>> adj;
	Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
	void addEdge(int a, int b, ll c, ll rcap = 0) {
		adj[a].push_back({b, sz(adj[b]), c, c});
		adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap});
	}
	ll dfs(int v, int t, ll f) {
		if (v == t || !f) return f;
		for (int& i = ptr[v]; i < sz(adj[v]); i++) {
			Edge& e = adj[v][i];
			if (lvl[e.to] == lvl[v] + 1)
				if (ll p = dfs(e.to, t, min(f, e.c))) {
					e.c -= p, adj[e.to][e.rev].c += p;
					return p;
				}
		}
		return 0;
	}
	ll calc(int s, int t) {
		ll flow = 0; q[0] = s;
		rep(L,30,31) do { // 'int L=30' maybe faster for random data
			lvl = ptr = vi(sz(q));
			int qi = 0, qe = lvl[s] = 1;
			while (qi < qe && !lvl[t]) {
				int v = q[qi++];
				for (Edge e : adj[v])
					if (!lvl[e.to] && e.c >> (30 - L))
						q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
			}
			while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
		} while (lvl[t]);
		return flow;
	}
	bool leftOfMinCut(int a) { return lvl[a] != 0; }
};

template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; }

typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ld,ld> pld;
typedef complex<ld> cd;

typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;

const ld PI = acos(-1.0);
const ld EPS = 1e-7;
const int MOD = 998244353;

int32_t main() { FAST
  int n;
  cin >> n;

  vector<string> board(n);
  F0R(i, n){
    cin >> board[i];
  }

  vector<int> r(n), c(n);
  F0R(i, n){
    cin >> r[i];
  }
  F0R(i, n){
    cin >> c[i];
  }

  F0R(i, n){
    F0R(j, n){
      if (board[i][j] == '-'){
        r[i]++;
        c[j]++;
      }
    }
  }

  int totr = 0;
  int totc = 0;
  F0R(i, n){
    totr += r[i];
    totc += c[i];
    if (r[i] < 0 || c[i] < 0){
      cout << "No\n";
      return 0;
    }
  }
  if (totr != totc){
    cout << "No\n";
    return 0;
  }

  int so = n + n;
  int si = n + n + 1;
  Dinic MF(n + n + 2);
  F0R(i, n){
    MF.addEdge(so, i, r[i]);
    MF.addEdge(i + n, si, c[i]);
  }
  F0R(i, n){
    F0R(j, n){
      MF.addEdge(i, j + n, 1);
    }
  }

  auto res = MF.calc(so, si);
  if (res != totc){
    cout << "No\n";
    return 0;
  }

  cout << "Yes\n";

  vvi out(n, vi(n));
  F0R(i, n){
    for(auto e : MF.adj[i]){
      if (e.to < so && e.flow()){
        out[i][e.to - n] = 1;
      }
    }
  }

  F0R(i, n){
    F0R(j, n){
      if (board[i][j] == '-'){
        out[i][j] ^= 1;
      }
      cout << out[i][j];
    }
    cout << '\n';
  }

  return 0;
}

Details

answer.code: In member function ‘int Dinic::Edge::flow()’:
answer.code:35:39: error: no matching function for call to ‘max(int, long long int)’
   35 |                 ll flow() { return max(oc - c, 0LL); } // if you need flows
      |                                    ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:35:39: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
   35 |                 ll flow() { return max(oc - c, 0LL); } // if you need flows
      |                                    ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:35:39: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
   35 |                 ll flow() { return max(oc - c, 0LL); } // if you need flows
      |                                    ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:35:39: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
   35 |                 ll flow() { return max(oc - c, 0LL); } // if you need flows
      |                                    ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:35:39: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
   35 |                 ll flow() { return max(oc - c, 0LL); } // if you need flows
      |                                    ~~~^~~~~~~~~~~~~
answer.code: In member function ‘int Dinic::calc(int, int)’:
answer.code:67:49: warning: overflow in conversion from ‘long long int’ to ‘int’ changes value from ‘9223372036854775807’ to ‘-1’ [-Woverflow]
   67 |                         while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
      |                                                 ^~~~~~~~~