結果

問題 No.241 出席番号(1)
ユーザー cormoran
提出日時 2016-08-23 22:00:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,178 bytes
コンパイル時間 1,810 ms
コンパイル使用メモリ 178,744 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 21:36:13
合計ジャッジ時間 3,101 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
const int INF = 1 << 30;
using Vatex = int;
template<typename Cost_t = ll>
class MaxFlow{
public:
vector< vector<Cost_t> > G; //
MaxFlow(int N) {
G.resize(N, vector<int>(N));
}
void add_arc(Vatex v1,Vatex v2,Cost_t capacity){
G[v1][v2] += capacity;
}
//now end
Cost_t dfs(Vatex now,Vatex end,Cost_t min_capacity,vector<bool> &visited){
if( now == end ) return min_capacity;
if( not visited[now] ){
visited[now] = true;
rep(i,G.size()){
if(G[now][i] > 0){//nowi
Cost_t ret = dfs(i, end, min(min_capacity,G[now][i]), visited);
if(ret > 0){//
G[now][i] -= ret;
G[i][now] += ret;
return ret;
}
}
}
return -2;//
}
else return -1;//
}
Cost_t get_maxFlow(Vatex start,Vatex end){
int ans = 0;
//
vector<bool> is_visited(G.size());
while(true){
rep(i,G.size())is_visited[i]=false;
int inc_f=dfs(start,end,INF,is_visited);
if(inc_f>0)ans+=inc_f;
else return ans;
}
}
};
class Solver {
public:
int N;
vector<int> A;
bool solve() {
cin >> N;
A.resize(N); cin >> A;
// 0 ~ 49 : no
// 50~ 99 : student
// 100 : root
// 101 : goal
MaxFlow<int> flow(102);
rep(i, N) {
rep(j, N) {
if(j != A[i]) flow.add_arc(j, i + 50, 1);
}
}
rep(i, N) flow.add_arc(100, i, 1);
rep(i, N) flow.add_arc(i + 50, 101, 1);
if(flow.get_maxFlow(100, 101) < N) {
cout << -1 << endl;
} else {
vector<int> ans(N);
rep(i, N) {
bool flg = false;
rep(j, N) {
if(flow.G[i + 50][j]) {
flg = true;
ans[i] = j;
break;
}
}
assert(flg);
}
rep(i, N) cout << ans[i] << endl;
}
return 0;
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
Solver s;
s.solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0