結果

問題 No.1436 Rgaph
ユーザー tarattata1tarattata1
提出日時 2021-03-20 09:59:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 3,979 bytes
コンパイル時間 1,200 ms
コンパイル使用メモリ 109,752 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-21 07:26:51
合計ジャッジ時間 4,155 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 31 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 1 ms
6,816 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 27 ms
6,820 KB
testcase_11 AC 20 ms
6,820 KB
testcase_12 AC 19 ms
6,816 KB
testcase_13 AC 20 ms
6,816 KB
testcase_14 AC 19 ms
6,820 KB
testcase_15 AC 10 ms
6,820 KB
testcase_16 AC 16 ms
6,820 KB
testcase_17 AC 4 ms
6,820 KB
testcase_18 AC 3 ms
6,820 KB
testcase_19 AC 3 ms
6,820 KB
testcase_20 AC 10 ms
6,820 KB
testcase_21 AC 8 ms
6,820 KB
testcase_22 AC 35 ms
6,816 KB
testcase_23 AC 20 ms
6,820 KB
testcase_24 AC 38 ms
6,816 KB
testcase_25 AC 60 ms
6,816 KB
testcase_26 AC 65 ms
6,816 KB
testcase_27 AC 65 ms
6,816 KB
testcase_28 AC 2 ms
6,820 KB
testcase_29 AC 19 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

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) 

//#define ATCODER
#ifdef ATCODER
#include <atcoder/all>
#endif

typedef long long ll;
typedef unsigned long long ull;
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;
#ifdef ATCODER
using namespace atcoder;
#endif

//
// 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;
    scanf("%d%d", &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;
        scanf("%d%d", &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> ans0(m);       // 長さnの0,1からなる配列。0,1それぞれR,Gを表す
            vector<int> flag(n);       // loopに使われたnodeに印をつける
            int curr = i * 2 + 1;
            int bad = 0;
            int tmp = 1;
            int dd = 0;
            while ( 1 ) {
                if (flag[curr/2]) {
                    bad = 1; break;   // 同じnodeを2回通るループは除外                    
                }
                else {
                    flag[curr / 2] = 1; dd++;
                }
                int prev = pr[curr];
                int edge = ed[make_pair(prev / 2, curr / 2)];
                ans0[edge] = tmp;
                if (dd==2) {
                    ans0[edge] = 1 - ans0[edge];
                }
                tmp = 1 - tmp;
                curr = prev;
                if (curr == i * 2) {
                    ans0[edge] = 1 - ans0[edge];
                    break;
                }
            }
            if (bad == 0) {
                ans.swap(ans0);
            }
        }
    }
    if (ans.empty()) {
        printf("-1"); return;
    }
    for(i=0;i<m;i++){
        if (ans[i] == 0) printf("R");
        else printf("G");
    }
    printf("\n");

    return;
}


int main()
{
#if 1
    solve();
#else    
    int T, t;
    scanf("%d", &T);
    for (t = 0; t < T; t++) {
        //cout << "Case #" << t + 1 << ": ";
        solve();
    }
#endif
    return 0;
}
0