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
AC × 3
AC × 51
AC × 68
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