結果

問題 No.241 出席番号(1)
ユーザー airisairis
提出日時 2015-07-11 02:07:59
言語 C++11
(gcc 11.4.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,689 bytes
コンパイル時間 3,257 ms
コンパイル使用メモリ 87,736 KB
実行使用メモリ 4,508 KB
最終ジャッジ日時 2023-08-13 14:23:44
合計ジャッジ時間 9,869 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘void Graph::add_edge(int, int, int)’:
main.cpp:51:48: warning: narrowing conversion of ‘(&((Graph*)this)->Graph::G.std::vector<std::vector<Edge> >::operator[](((std::vector<std::vector<Edge> >::size_type)to)))->std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ inside { } [-Wnarrowing]
    G[from].push_back((Edge){to, cap, G[to].size()});
                                      ~~~~~~~~~~^~
main.cpp:52:51: warning: narrowing conversion of ‘((&((Graph*)this)->Graph::G.std::vector<std::vector<Edge> >::operator[](((std::vector<std::vector<Edge> >::size_type)from)))->std::vector<Edge>::size() - 1)’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ inside { } [-Wnarrowing]
    G[to].push_back((Edge){from, 0, G[from].size() - 1});
                                    ~~~~~~~~~~~~~~~^~~
main.cpp: In member function ‘int Graph::bfs(int)’:
main.cpp:71:3: warning: no return statement in function returning non-void [-Wreturn-type]
   }
   ^

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <numeric>
#include <bitset>
#include <complex>
#define rep(x, to) for (int x = 0; x < (to); x++)
#define REP(x, a, to) for (int x = (a); x < (to); x++)
#define foreach(itr, x) for (typeof((x).begin()) itr = (x).begin(); itr != (x).end(); itr++)
#define EPS (1e-14)

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef complex<double> Complex;
typedef vector< vector<int> > Mat;

int N;
int a[55];

struct Edge {
	int to;
	int cap;
	int rev;
};

class Graph {
	public:
		vector < vector<Edge> > G;
		vector<int> level;
		vector<int> iter;

		Graph(int n) {
			G.resize(n + 5);
			level.resize(n + 5, 0);
			iter.resize(n + 5, 0);
		}

		void add_edge(int from, int to, int cap) {
			G[from].push_back((Edge){to, cap, G[to].size()});
			G[to].push_back((Edge){from, 0, G[from].size() - 1});
		}

		//s:source
		int bfs(int s) {
			for (int i = 0; i < level.size(); i++) level[i] = -1;
			queue<int> que;
			level[s] = 0;
			que.push(s);
			while (!que.empty()) {
				int v = que.front(); que.pop();
				for (int i = 0; i < G[v].size(); i++) {
					Edge &e = G[v][i];
					if (e.cap > 0 && level[e.to] < 0) {
						level[e.to] = level[v] + 1;
						que.push(e.to);
					}
				}
			}
		}

		//t:sink
		int dfs(int v, int t, int f) {
			if (v == t) return f;
			for (int &i = iter[v]; i < G[v].size(); i++) {
				Edge &e = G[v][i];
				if (e.cap > 0 && level[v] < level[e.to]) {
					int d = dfs(e.to, t, min(f, e.cap));
					if (d > 0) {
						e.cap -= d;
						G[e.to][e.rev].cap += d;
						return d;
					}
				}
			}
			return 0;
		}

		//s:source
		//t:sink
		int max_flow(int s, int t) {
			int flow = 0;
			for (;;) {
				bfs(s);
				if (level[t] < 0) return flow;
				for (int i = 0; i < iter.size(); i++) iter[i] = 0;
				int f;
				while (f = dfs(s, t, 1e+9 + 7)) {
					flow += f;
				}
			}
		}
};



void solve() {
	Graph graph(105);
	int S = N + N;
	int T = N + N + 1;
	//u -> v;
	rep(i, N) {
		rep(j, N) {
			if (j == a[i]) continue;
			graph.add_edge(i, j + N, 1);
		}
	}
	//S -> u; v -> T;
	rep(i, N) {
		graph.add_edge(S, i, 1);
		graph.add_edge(i + N, T, 1);
	}
	int flow = graph.max_flow(S, T);
	if (flow != N) {
		cout << -1 << endl;
	} else {
		rep(i, N) {
			rep(j, graph.G[i].size()) {
				Edge &e = graph.G[i][j];
				if (graph.G[e.to][e.rev].cap > 0) {
					cout << e.to - N << endl;
					break;
				}
			}
		}
	}
}

int main() {
	cin >> N;
	rep(i, N) cin >> a[i];
	solve();
	return 0;
}
0