結果

問題 No.241 出席番号(1)
ユーザー airis
提出日時 2015-07-11 02:07:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,689 bytes
コンパイル時間 1,119 ms
コンパイル使用メモリ 95,484 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-21 10:06:11
合計ジャッジ時間 10,693 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘void Graph::add_edge(int, int, int)’:
main.cpp:51:69: 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’ [-Wnarrowing]
   51 |                         G[from].push_back((Edge){to, cap, G[to].size()});
      |                                                           ~~~~~~~~~~^~
main.cpp:52:72: 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’ [-Wnarrowing]
   52 |                         G[to].push_back((Edge){from, 0, G[from].size() - 1});
      |                                                         ~~~~~~~~~~~~~~~^~~
main.cpp: In member function ‘int Graph::bfs(int)’:
main.cpp:71:17: warning: no return statement in function returning non-void [-Wreturn-type]
   71 |                 }
      |                 ^

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0