Submission #573179
Source Code Expand
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
using namespace std;
typedef struct{
int to;
int cap;
int rev;
}edge;
// node v : distance from s => level[v]
void bfs(vector<vector<edge> > &G, vector<int> &level, int s){
fill(level.begin(), level.end(), -1);
queue<int> q;
q.push(s);
level[s] = 0;
while(!q.empty()){
int e=q.front(); q.pop();
for(int i=0; i<G[e].size(); i++){
if(G[e][i].cap > 0 && level[G[e][i].to] < 0){
level[G[e][i].to] = level[e] + 1;
q.push(G[e][i].to);
}
}
}
}
int dfs(vector<vector<edge> > &G, vector<int> &level, vector<bool> &used, vector<int> &iter, int s, int f, int t){
if(s==t) return f;
else{
//iter[e] : done searching from v[0] to v[ iter[e]-1 ]
for(int &i=iter[s]; i<G[s].size(); i++){
//distance from s to v[e][i].to must be longer than dist from s to v
if(G[s][i].cap > 0 && level[s] < level[ G[s][i].to ]){
int d = dfs(G, level, used, iter, G[s][i].to, min(f, G[s][i].cap), t);
if(d>0){
G[s][i].cap -= d;
G[ G[s][i].to ][ G[s][i].rev ].cap += d;
return d;
}
}
}
return 0;
}
}
int dinic_maxflow(vector<vector<edge> > &G, int s, int t){
const int INF = 100000000;
int flow=0;
while(true){
vector<int> level(G.size(), -1);
vector<int> iter(G.size(), 0);
vector<bool> used(G.size(), false);
bfs(G, level, s);
if(level[t] < 0) return flow; //unable to achieve to t
while(true){
int f = dfs(G, level, used, iter, s, INF, t);
if(f==0) break;
else flow += f;
}
}
}
void add_edge(vector<vector<edge> > &G, int from, int to, int cap){
G[from].push_back((edge){to, cap, (int)G[to].size()});
G[to].push_back((edge){from, 0, (int)G[from].size() - 1});
}
class SCC{
int n;
vector<vector<int> > G;
vector<vector<int> > rG;
void dfs(vector<bool> &visit, int pos, vector<int> &result){
visit[pos] = true;
for(int i=0; i<G[pos].size(); i++){
if(visit[ G[pos][i] ]) continue;
dfs(visit, G[pos][i], result);
}
result.push_back(pos);
}
void rdfs(vector<bool> &visit, int pos, int k){
visit[pos] = true;
component[pos] = k;
for(int i=0; i<rG[pos].size(); i++){
if(visit[ rG[pos][i] ]) continue;
rdfs(visit, rG[pos][i], k);
}
}
void make_rev(vector<vector<int> > &G){
for(int i=0; i<n; i++){
for(int j=0; j<G[i].size(); j++){
rG[ G[i][j] ].push_back(i);
}
}
}
public:
int num_components;
vector<int> component;
vector< vector<int> > scc_graph;
SCC(int n){
this->n = n;
G.resize(n);
rG.resize(n);
}
SCC(vector<vector<int> > &G){
this->n = G.size();
this->G = G;
rG.resize(n);
make_rev(G);
}
void strongly_connected_components(){
vector<bool> visit(n, false);
vector<int> result;
for(int i=0; i<n; i++){
if(visit[i]) continue;
dfs(visit, i, result);
}
component.resize(n);
fill(visit.begin(), visit.end(), false);
int k=0;
for(int i=result.size()-1; i>=0; i--){
if(visit[ result[i] ]) continue;
rdfs(visit, result[i], k);
k++;
}
num_components = k;
scc_graph.resize( num_components );
for(int i=0; i<n; i++){
int cmp = component[i];
for(int j=0; j<G[i].size(); j++){
if(component[ G[i][j] ] == cmp) continue;
scc_graph[cmp].push_back( component[ G[i][j] ] );
}
}
for(int i=0; i<scc_graph.size(); i++){
sort(scc_graph[i].begin(), scc_graph[i].end());
scc_graph[i].erase( unique(scc_graph[i].begin(), scc_graph[i].end()), scc_graph[i].end());
}
}
void add_edge(int from, int to){
G[from].push_back(to);
rG[to].push_back(from);
}
};
#include <cassert>
template<class T>
ostream& operator << (ostream& os, vector<T> vec){
for(int i=0; i<vec.size(); i++){
os << vec[i] << " ";
}
os << endl;
return os;
}
int main(){
int n,m;
cin >> n >> m;
vector<int> a(m),b(m);
map<pair<int,int>, int> E;
for(int i=0; i<m; i++){
scanf("%d%d", &a[i],&b[i]);
a[i]--; b[i]--;
E[{a[i],b[i]}] += 1;
}
assert(n>1);
vector<vector<edge>> G(n);
int s = 0;
int t = n-1;
for(int i=0; i<m; i++){
add_edge(G, a[i], b[i], 1);
}
// for(auto itr=E.begin(); itr!=E.end(); itr++){
// add_edge(G, itr->first.first, itr->first.second, itr->second);
// }
int f = dinic_maxflow(G, s,t);
vector<vector<int>> g(n);
for(int i=0; i<n; i++){
for(edge& e:G[i]){
if(e.cap == 0) continue;
g[i].push_back(e.to);
}
}
SCC scc(g);
scc.strongly_connected_components();
vector<int>& cmp = scc.component;
assert(cmp[0] != cmp[n-1]);
vector<bool> is_zero(scc.scc_graph.size(), false);
{
queue<int> q_;
q_.push(cmp[0]);
is_zero[cmp[0]] = true;
while(q_.size()){
int pos = q_.front();
q_.pop();
for(int to:scc.scc_graph[pos]){
if(is_zero[to]) continue;
q_.push(to);
is_zero[to] = true;
}
}
//is_zero[component] == true ならば cmp[0] と同じ要素
}
//逆グラフ
vector<vector<int>> rev_scc(scc.scc_graph.size());
for(int i=0; i<scc.scc_graph.size(); i++){
for(int to:scc.scc_graph[i]){
rev_scc[to].push_back(i);
}
}
vector<bool> is_last(scc.scc_graph.size(), false);
{
queue<int> q_;
q_.push(cmp[n-1]);
is_last[cmp[n-1]] = true;
while(q_.size()){
int pos = q_.front();
q_.pop();
for(int to:rev_scc[pos]){
if(is_last[to]) continue;
q_.push(to);
is_last[to] = true;
}
}
//is_last[component] == true ならば cmp[n-1] と同じ要素
}
vector<int> state(n,0);
for(int i=0; i<n; i++){
if(cmp[i] == cmp[0]) state[i] |= 1;
if(cmp[i] == cmp[n-1]) state[i] |= 2;
if(is_zero[cmp[i]]) state[i] = 1;
if(is_last[cmp[i]]) state[i] = 2;
}
int q;
cin >> q;
while(q--){
int c,d;
scanf("%d%d", &c,&d);
c--; d--;
int same = (state[c] == state[d]) || (state[c] == 0 || state[d] == 0);
int diff = cmp[c] != cmp[d] && ((state[c] != state[d]) || (state[c] == 0 || state[d] == 0));
printf("%s %s\n", same?"YES":"NO", diff?"YES":"NO");
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 高橋王国と青木王国 |
User |
koyumeishi |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
6329 Byte |
Status |
AC |
Exec Time |
181 ms |
Memory |
7452 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:189:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i],&b[i]);
^
./Main.cpp:277:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &c,&d);
^
Judge Result
Set Name |
Sample |
Dataset1 |
Dataset2 |
Score / Max Score |
0 / 0 |
20 / 20 |
80 / 80 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt |
Dataset1 |
00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 01_30.txt, 01_31.txt, 01_32.txt, 01_33.txt, 01_34.txt, 01_35.txt, 01_36.txt, 01_37.txt, 01_38.txt, 01_39.txt, 01_40.txt, 01_41.txt, 01_42.txt, 01_43.txt, 01_44.txt, 01_45.txt, 01_46.txt, 01_47.txt |
Dataset2 |
00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 01_30.txt, 01_31.txt, 01_32.txt, 01_33.txt, 01_34.txt, 01_35.txt, 01_36.txt, 01_37.txt, 01_38.txt, 01_39.txt, 01_40.txt, 01_41.txt, 01_42.txt, 01_43.txt, 01_44.txt, 01_45.txt, 01_46.txt, 01_47.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample_01.txt |
AC |
33 ms |
780 KB |
00_sample_02.txt |
AC |
27 ms |
800 KB |
00_sample_03.txt |
AC |
27 ms |
792 KB |
01_00.txt |
AC |
29 ms |
920 KB |
01_01.txt |
AC |
27 ms |
920 KB |
01_02.txt |
AC |
27 ms |
788 KB |
01_03.txt |
AC |
26 ms |
804 KB |
01_04.txt |
AC |
27 ms |
836 KB |
01_05.txt |
AC |
34 ms |
840 KB |
01_06.txt |
AC |
28 ms |
920 KB |
01_07.txt |
AC |
27 ms |
924 KB |
01_08.txt |
AC |
27 ms |
796 KB |
01_09.txt |
AC |
27 ms |
940 KB |
01_10.txt |
AC |
27 ms |
928 KB |
01_11.txt |
AC |
25 ms |
936 KB |
01_12.txt |
AC |
24 ms |
920 KB |
01_13.txt |
AC |
26 ms |
812 KB |
01_14.txt |
AC |
26 ms |
804 KB |
01_15.txt |
AC |
26 ms |
800 KB |
01_16.txt |
AC |
26 ms |
788 KB |
01_17.txt |
AC |
26 ms |
920 KB |
01_18.txt |
AC |
28 ms |
800 KB |
01_19.txt |
AC |
28 ms |
924 KB |
01_20.txt |
AC |
28 ms |
784 KB |
01_21.txt |
AC |
27 ms |
928 KB |
01_22.txt |
AC |
27 ms |
936 KB |
01_23.txt |
AC |
28 ms |
872 KB |
01_24.txt |
AC |
27 ms |
928 KB |
01_25.txt |
AC |
27 ms |
928 KB |
01_26.txt |
AC |
27 ms |
924 KB |
01_27.txt |
AC |
27 ms |
792 KB |
01_28.txt |
AC |
26 ms |
800 KB |
01_29.txt |
AC |
25 ms |
804 KB |
01_30.txt |
AC |
28 ms |
924 KB |
01_31.txt |
AC |
26 ms |
800 KB |
01_32.txt |
AC |
26 ms |
804 KB |
01_33.txt |
AC |
26 ms |
804 KB |
01_34.txt |
AC |
24 ms |
928 KB |
01_35.txt |
AC |
24 ms |
796 KB |
01_36.txt |
AC |
26 ms |
800 KB |
01_37.txt |
AC |
25 ms |
796 KB |
01_38.txt |
AC |
27 ms |
804 KB |
01_39.txt |
AC |
27 ms |
924 KB |
01_40.txt |
AC |
25 ms |
896 KB |
01_41.txt |
AC |
26 ms |
800 KB |
01_42.txt |
AC |
24 ms |
920 KB |
01_43.txt |
AC |
27 ms |
800 KB |
01_44.txt |
AC |
25 ms |
916 KB |
01_45.txt |
AC |
26 ms |
912 KB |
01_46.txt |
AC |
25 ms |
924 KB |
01_47.txt |
AC |
26 ms |
800 KB |
02_00.txt |
AC |
105 ms |
2720 KB |
02_01.txt |
AC |
101 ms |
2724 KB |
02_02.txt |
AC |
116 ms |
2980 KB |
02_03.txt |
AC |
139 ms |
4008 KB |
02_04.txt |
AC |
176 ms |
7452 KB |
02_05.txt |
AC |
181 ms |
7068 KB |
02_06.txt |
AC |
172 ms |
6816 KB |
02_07.txt |
AC |
141 ms |
5080 KB |
02_08.txt |
AC |
152 ms |
5600 KB |
02_09.txt |
AC |
157 ms |
5600 KB |
02_10.txt |
AC |
149 ms |
5600 KB |
02_11.txt |
AC |
130 ms |
6312 KB |
02_12.txt |
AC |
128 ms |
5788 KB |
02_13.txt |
AC |
128 ms |
5032 KB |
02_14.txt |
AC |
124 ms |
5160 KB |
02_15.txt |
AC |
122 ms |
5540 KB |
02_16.txt |
AC |
127 ms |
5412 KB |