結果

問題 No.1436 Rgaph
ユーザー tarattata1
提出日時 2021-03-20 09:52:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 3,959 bytes
コンパイル時間 1,447 ms
コンパイル使用メモリ 110,924 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-21 07:26:27
合計ジャッジ時間 4,465 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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) 
//#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
vector<int> bfs(int s, const vector<vector<int>>& G, vector<int>* ppr)
{   // G[from]={to} の形のグラフ。pprは最短距離のときのprevを記録
    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<vector<int>> f(n);     // f[to]={from} の形のグラフ。
    vector<int> a(m), b(m);
    map<pair<int, int>, int> ed;   // (from,to)->edgeid
    int i, j;
    for (i = 0; i < m; i++) {
        scanf("%d%d", &a[i], &b[i]); a[i]--; b[i]--;
        ed[make_pair(a[i], b[i])] = i;
        f[b[i]].push_back(a[i]);
        g[a[i]*2].push_back(b[i]*2+1);
        g[a[i]*2+1].push_back(b[i]*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() && f[i].size() > 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0