답안 #124977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
124977	2019-07-04T08:53:52 Z	semiauto	One-Way Streets (CEOI17_oneway)	C++14	컴파일 오류	0 ms	0 KB

oneway

#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,t,i,who,k,q;
char ch[100001];
vector <int> v[100001];
vector <pair <int,pair <int,int> > > gr[100001];
bool fix[100001],block[100001],isbridge[100001];
int tin[100001],low[100001],parent[100001],in[100001],out[100001],aloup[100001],alodown[100001],A[100001],B[100001],p[100001][17];
unordered_map <pair<int,int>,int> mymap;
void dfsjust(int a,int c) {
    parent[a]=c;
    int i;
    for (i=0;i<v[a].size();i++) {
        if (parent[v[a][i]] && parent[v[a][i]]!=c && isbridge[mymap[{a,v[a][i]}]]) {
            gr[c].push_back({parent[v[a][i]],{a,v[a][i]}});
            gr[parent[v[a][i]]].push_back({c,{v[a][i],a}});
        }
        if (!parent[v[a][i]] && !isbridge[mymap[{a,v[a][i]}]])
            dfsjust(v[a][i],c);
    }
}
void justdfs(int a) {
    fix[a]=1;
    int i;
    for (i=0;i<v[a].size();i++)
        if (!fix[v[a][i]])
            justdfs(v[a][i]);
}
void dfs(int a,int b) {
    fix[a]=1;
    tin[a]=low[a]=t++;
    int i;
    for (i=0;i<v[a].size();i++) {
        if (v[a][i]==b)
            continue;
        if (fix[v[a][i]])
            low[a]=min(low[a],tin[v[a][i]]);
        else {
            dfs(v[a][i],a);
            low[a]=min(low[a],low[v[a][i]]);
            if (low[v[a][i]]>tin[a])
                isbridge[mymap[{a,v[a][i]}]]=1;
        }
    }
}
void go(int a,int b) {
    in[a]=t++;
    p[a][0]=b;
    int i;
    for (i=1;i<17;i++)
        p[a][i]=p[p[a][i-1]][i-1];
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b)
            go(gr[a][i].first,a);
    out[a]=t++;
}
bool isp(int a,int b) {
    if (in[a]<=in[b] && out[a]>=out[b])
        return true;
    return false;
}
int lca(int c,int b) {
    int x=1,i;
    for (i=16;i>=0;i--)
        if (p[c][i] && !isp(p[c][i],b)) {
            c=p[c][i];
            x+=(1<<i);
        }
    return x;
}
void gogo(int a,int b) {
    int i;
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b) {
            if (aloup[gr[a][i].first] || alodown[gr[a][i].first]) {
                int hey=mymap[{gr[a][i].second.first,gr[a][i].second.second}];
                if (aloup[gr[a][i].first])
                    swap(A[hey],B[hey]);
                if (gr[a][i].second.second==B[hey])
                    ch[hey]='R';
                else
                    ch[hey]='L';

            }
            gogo(gr[a][i].first,a);
    }
}
int goup(int a,int b) {
    int i,x=0;
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b)
            x=max(x,goup(gr[a][i].first,a));
    return aloup[a]=max(aloup[a],x-1);
}
int godown(int a,int b) {
    int i,x=0;
    for (i=0;i<gr[a].size();i++)
        if (gr[a][i].first!=b)
            x=max(x,godown(gr[a][i].first,a));
    return alodown[a]=max(alodown[a],x-1);
}
int main() {
    cin>>n>>m;
    for (i=1;i<=m;i++) {
        ch[i]='B';
        cin>>a>>b;
        A[i]=a;B[i]=b;
        if (a==b)
            continue;
        if (mymap[{a,b}])
            block[mymap[{a,b}]]=block[mymap[{b,a}]]=1;
        else {
            v[a].push_back(b);
            v[b].push_back(a);
            mymap[{a,b}]=mymap[{b,a}]=i;
        }
    }
    for (i=1;i<=n;i++) {
        if (!fix[i])
            justdfs(i);
        else
            continue;
        if (who) {
            v[who].push_back(i);
            v[i].push_back(who);
        }
        else
            who=i;
    }
    for (i=1;i<=n;i++)
        fix[i]=0;
    for (i=1;i<=n;i++)
        if (!fix[i])
            dfs(i,-1);
    for (i=1;i<=n;i++)
        if (!parent[i])
            dfsjust(i,++k);
    go(1,0);
    cin>>q;
    for (i=1;i<=q;i++) {
        cin>>a>>b;
        a=parent[a];
        b=parent[b];
        if (!isp(a,b))
            aloup[a]=max(aloup[a],lca(a,b));
        if (!isp(b,a))
            alodown[b]=max(alodown[b],lca(b,a));
    }
    aloup[1]=goup(1,0);
    alodown[1]=godown(1,0);
    gogo(1,0);
    for (i=1;i<=m;i++) {
        if (block[mymap[{A[i],B[i]}]])
            ch[i]='B';
        cout<<ch[i];
    }
    cout<<endl;
}

Compilation message

In file included from /usr/include/c++/7/bits/hashtable.h:35:0,
                 from /usr/include/c++/7/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from oneway.cpp:1:
/usr/include/c++/7/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > >':
/usr/include/c++/7/type_traits:143:12:   required from 'struct std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > >'
/usr/include/c++/7/type_traits:154:31:   required from 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
/usr/include/c++/7/bits/unordered_map.h:103:66:   required from 'class std::unordered_map<std::pair<int, int>, int>'
oneway.cpp:9:35:   required from here
/usr/include/c++/7/bits/hashtable_policy.h:87:34: error: no match for call to '(const std::hash<std::pair<int, int> >) (const std::pair<int, int>&)'
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from oneway.cpp:1:
/usr/include/c++/7/type_traits: In instantiation of 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >':
/usr/include/c++/7/bits/unordered_map.h:103:66:   required from 'class std::unordered_map<std::pair<int, int>, int>'
oneway.cpp:9:35:   required from here
/usr/include/c++/7/type_traits:154:31: error: 'value' is not a member of 'std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > >'
     : public __bool_constant<!bool(_Pp::value)>
                               ^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/unordered_map:48:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from oneway.cpp:1:
/usr/include/c++/7/bits/unordered_map.h: In instantiation of 'class std::unordered_map<std::pair<int, int>, int>':
oneway.cpp:9:35:   required from here
/usr/include/c++/7/bits/unordered_map.h:103:66: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
                                                                  ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:110:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::key_type key_type;
                                             ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:111:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::value_type value_type;
                                               ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:112:48: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::mapped_type mapped_type;
                                                ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:113:43: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::hasher hasher;
                                           ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:114:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::key_equal key_equal;
                                              ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:115:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::allocator_type allocator_type;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:120:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::pointer  pointer;
                                             ^~~~~~~
/usr/include/c++/7/bits/unordered_map.h:121:50: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::const_pointer const_pointer;
                                                  ^~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:122:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::reference  reference;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:123:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::const_reference const_reference;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:124:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::iterator  iterator;
                                              ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:125:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::const_iterator const_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:126:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::local_iterator local_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:127:57: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::const_local_iterator const_local_iterator;
                                                         ^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:128:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::size_type  size_type;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:129:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       typedef typename _Hashtable::difference_type difference_type;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:288:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       operator=(initializer_list<value_type> __l)
       ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:386:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
  emplace(_Args&&... __args)
  ^~~~~~~
/usr/include/c++/7/bits/unordered_map.h:578:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       insert(const value_type& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:584:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       insert(value_type&& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:591:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
  insert(_Pair&& __x)
  ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:657:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       insert(initializer_list<value_type> __l)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:953:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       equal_range(const key_type& __x)
       ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:957:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<int, int> > >, std::__detail::__is_noexcept_hash<std::pair<int, int>, std::hash<std::pair<int, int> > > > >'
       equal_range(const key_type& __x) const
       ^~~~~~~~~~~
oneway.cpp: In function 'void dfsjust(int, int)':
oneway.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp:14:68: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
         if (parent[v[a][i]] && parent[v[a][i]]!=c && isbridge[mymap[{a,v[a][i]}]]) {
                                                                    ^
oneway.cpp:18:48: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
         if (!parent[v[a][i]] && !isbridge[mymap[{a,v[a][i]}]])
                                                ^
oneway.cpp: In function 'void justdfs(int)':
oneway.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[a].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp:42:31: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
                 isbridge[mymap[{a,v[a][i]}]]=1;
                               ^
oneway.cpp: In function 'void go(int, int)':
oneway.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'void gogo(int, int)':
oneway.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp:76:30: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
                 int hey=mymap[{gr[a][i].second.first,gr[a][i].second.second}];
                              ^
oneway.cpp: In function 'int goup(int, int)':
oneway.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'int godown(int, int)':
oneway.cpp:97:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<gr[a].size();i++)
              ~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:110:18: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
         if (mymap[{a,b}])
                  ^
oneway.cpp:111:24: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
             block[mymap[{a,b}]]=block[mymap[{b,a}]]=1;
                        ^
oneway.cpp:111:44: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
             block[mymap[{a,b}]]=block[mymap[{b,a}]]=1;
                                            ^
oneway.cpp:115:18: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
             mymap[{a,b}]=mymap[{b,a}]=i;
                  ^
oneway.cpp:115:31: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
             mymap[{a,b}]=mymap[{b,a}]=i;
                               ^
oneway.cpp:153:24: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
         if (block[mymap[{A[i],B[i]}]])
                        ^