結果

問題 No.1436 Rgaph
ユーザー tarattata1
提出日時 2021-03-20 17:57:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 3,478 bytes
コンパイル時間 1,217 ms
コンパイル使用メモリ 110,940 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-21 07:27:01
合計ジャッジ時間 4,051 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <ctime>
#pragma warning(disable:4996) 

typedef long long ll;
#define INF 2140000000

using namespace std;

//
// G[from]={toの集合} というグラフと始点 s を入力。
// 始点sから各点への距離を求める。pprは最短距離のときのprevを記録
//
vector<int> bfs(int s, const vector<vector<int>>& G, vector<int>* ppr)
{
    queue<int> que;
    vector<int> d(G.size(), INF);
    if(ppr) ppr->resize(G.size(), -1);
    d[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int curr = que.front(); que.pop();
        int i;
        for (i = 0; i < (int)G[curr].size(); i++) {
            int next = G[curr][i];
            if (d[curr] + 1 < d[next]) {
                d[next] = d[curr] + 1;
                if(ppr) (*ppr)[next] = curr;
                que.push(next);
            }
        }
    }
    return d;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n*2);    // g[from]={to} の形のグラフ。ただし頂点を倍加（始点からの移動距離が偶数/奇数を区別）
    vector<int> cntin(n);          // 入次数をカウント
    map<pair<int, int>, int> ed;   // (from,to)->edgeid
    int i, j;
    for (i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        ed[make_pair(a, b)] = i;
        cntin[b]++;
        g[a*2].push_back(b*2+1);
        g[a*2+1].push_back(b*2);
    }
    vector<int> ans;    // 長さnの0,1からなる配列。0,1それぞれR,Gを表す
    for (i = 0; i < n; i++) {
        vector<int> pr;
        vector<int> dist = bfs(2 * i, g, &pr);
        for (j = 0; j < n; j++) {
            if (dist[j * 2] == INF && dist[j * 2 + 1] == INF) {
                printf("-1"); return;
            }
        }
        if (ans.empty() && cntin[i] > 1 && dist[i * 2 + 1] < INF) {   // 奇数閉路で、かつ i に他からも有向辺が来ている
            vector<int> flag(n);       // loopに使われたnodeに印をつける
            vector<int> loop;
            int curr = i * 2 + 1;
            int bad = 0;
            while (curr != i * 2 ) {
                if (flag[curr/2]) {
                    bad = 1; break;   // 同じnodeを2回通るループは除外                    
                }
                else {
                    flag[curr / 2] = 1;
                }
                int prev = pr[curr];
                int edge = ed[make_pair(prev / 2, curr / 2)];
                loop.push_back(edge);
                curr = prev;
            }
            if (bad == 0) {
                vector<int> ans0(m);                     // 長さmの0,1からなる配列。0,1それぞれR,Gを表す
                for(j=0; j<=(int)loop.size()/2; j++){    // ループの長さを 2k+1 とするとき、後半の(k+1)個だけ1をセット。それ以外は全て0
                    ans0[loop[j]]=1;
                }
                ans.swap(ans0);
            }
        }
    }
    if (ans.empty()) {
        cout << "-1" << endl; return;
    }
    for(i=0;i<m;i++){
        if (ans[i] == 0) cout << "R";
        else cout << "G";
    }
    cout << endl;

    return;
}

int main()
{
    solve();
    return 0;
}
0