QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#131355#1195. One-Way ConveyorsKLPP#WA 5ms30128kbC++204.9kb2023-07-27 00:02:552023-07-27 00:02:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-27 00:02:59]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:30128kb
  • [2023-07-27 00:02:55]
  • 提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)


// Be careful with duplicate edges! This algorithm only works with NO duplicate edges
struct Bridges {
  vector<int> disc, low;   vector<pair<int, int> > is_bridge;
  int Time;
  Bridges(vector< vector<int> > &adj) {
    disc = low = vector<int> ((int) adj.size());
    is_bridge.clear();   Time = 0;
    for (int i = 0; i < (int) adj.size(); i++) if (!disc[i]) dfs(adj, i);
  }
  void dfs(vector< vector<int> > &graph, int node, int p = -1) {
    disc[node] = low[node] = ++Time;
    for (auto to : graph[node]) {
      if (to == p) continue;
      if (!disc[to]) {
		  
        dfs(graph, to, node);   low[node] = min(low[node], low[to]);
        //cout<<node<<" "<<to<<endl;
        //cout<<disc[node]<<"A "<<low[to]<<endl;
        if (disc[node] < low[to]){
			is_bridge.emplace_back(node, to);
		}
      } else{
		  //cout<<node<<" "<<to<<" "<<p<<endl;
		  low[node] = min(low[node], disc[to]);
	  }
    }
    //cout<<node<<"B"<<low[node]<<" "<<p<<endl;
  }
};
vector<int> nei2[1000000];
int dfscount[1000000];
int cnt;
vector<pair<int,int> >edg;
int comp[1000000];
void DFS(int node){
	dfscount[node]=cnt;
	cnt++;
	trav(a,nei2[node]){
		if(dfscount[a]==-1){
			comp[a]=comp[node];
			DFS(a);
			edg.push_back({node,a});
		}else{
			if(dfscount[a]<dfscount[node]){
				edg.push_back({node,a});
			}
		}
	}
}

struct LCA {
  const int N, LOG;
  vector<int> depth;
  vector< vector<int> > dp;
  vector<int> parent;
  LCA(vector< vector<int> > &g) : N( (int)g.size() ), LOG( (int) log2(N)+1) {
    dp = vector< vector<int> > (N, vector<int> (LOG, -1) );
    depth = vector<int> (N, 0);
    parent = vector<int> (N, -1);
    dfs (g, 0);
    for (int j = 1; j < LOG; j++) {
      for (int i = 0; i < N; i++)
        if (dp[i][j - 1] != -1) dp[i][j] = dp[ dp[i][j - 1] ][j - 1];
    }
  }
  void dfs (vector< vector<int> > &g, int node, int p = -1) {
    dp[node][0] = p;
    for (auto to : g[node])
      if (to != p) { depth[to] = depth[node] + 1; parent[to]=node; dfs (g, to, node); }
  }
  // Edge weight = 1, otherwise change depth by sum till root
  int dist (int u, int v) { return depth[u] + depth[v] - 2 * depth[lca (u, v)]; }
  int kth (int u, int diff) {
    for (int i = LOG - 1; i >= 0; i--) if ((diff >> i) & 1) u = dp[u][i];
    return u;
  }
  int lca (int u, int v) {
    if (depth[u] < depth[v]) swap (u, v);
    u = kth (u, depth[u] - depth[v]);
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; i--)
      if (dp[u][i] != dp[v][i]) u = dp[u][i], v = dp[v][i];
    return dp[u][0];
  }
};


void solve(){
	int n,m;
	cin>>n>>m;
	vector<vector<int> >nei(n);
	rep(i,0,m){
		int x,y;
		cin>>x>>y;
		x--;y--;
		//cout<<x<<" "<<y<<endl;
		nei[x].push_back(y);
		nei[y].push_back(x);
	}
	int q;
	cin>>q;
	vector<pair<int,int> >pairs(q);
	rep(i,0,q)cin>>pairs[i].first>>pairs[i].second,pairs[i].first--,pairs[i].second--;
	Bridges B(nei);
	//cout<<B.is_bridge.size()<<endl;
	set<pair<int,int> >br;
	trav(a,B.is_bridge){
		//cout<<a.first<<" "<<a.second<<endl;
		br.insert(a);
	}
	rep(i,0,n){
		trav(a,nei[i]){
			if(br.find({a,i})==br.end() && br.find({i,a})==br.end()){
				nei2[i].push_back(a);
			}
		}
	}
	cnt=0;
	rep(i,0,n)dfscount[i]=-1;
	int cc=0;
	rep(i,0,n){
		if(dfscount[i]==-1){
			comp[i]=cc;
			cc++;
			DFS(i);
		}
	}
	vector<vector<int> >nei3(cc);
	rep(i,0,n){
		trav(a,nei[i]){
			if(comp[a]!=comp[i]){
				nei3[comp[a]].push_back(comp[i]);
			}
		}
	}
	map<pair<int,int>,pair<int,int> >M;
	trav(a,B.is_bridge){
		M[{comp[a.first],comp[a.second]}]=a;
		M[{comp[a.second],comp[a.first]}]=pair<int,int>(a.second,a.first);
	}
	LCA L(nei3);
	vector<int> D(cc,0);
	vector<int> U(cc,0);
	rep(i,0,q){
		int x=comp[pairs[i].first];
		int y=comp[pairs[i].second];
		if(x==y)continue;
		int lc=L.lca(x,y);
		U[x]=max(U[x],L.depth[x]-L.depth[lc]);
		D[y]=max(D[y],L.depth[y]-L.depth[lc]);
	}
	vector<pair<int,int> >order;
	rep(i,0,cc)order.push_back({L.depth[i],i});
	sort(order.begin(),order.end());
	reverse(order.begin(),order.end());
	trav(a,order){
		int ver=a.second;
		int par=L.parent[ver];
		if(par==-1)continue;
		U[par]=max(U[par],U[ver]-1);
		D[par]=max(D[par],D[ver]-1);
		if(D[ver]>0 && U[ver]>0){
			cout<<"No\n";
			return;
		}
		if(D[ver]>0){
			edg.push_back(M[pair<int,int>(par,ver)]);
		}else edg.push_back(M[{ver,par}]);
	}
	cout<<"Yes\n";
	trav(a,edg)cout<<a.first+1<<" "<<a.second+1<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	//cin>>tt;
	while(tt--){
		solve();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 30128kb

input:

3 2
1 2
2 3
3
1 2
1 3
2 3

output:

Yes
2 3
1 2

result:

ok OK!

Test #2:

score: 0
Accepted
time: 5ms
memory: 30076kb

input:

3 2
1 2
2 3
3
1 2
1 3
3 2

output:

No

result:

ok OK!

Test #3:

score: -100
Wrong Answer
time: 4ms
memory: 29588kb

input:

4 4
1 2
1 3
1 4
2 3
7
1 2
1 3
1 4
2 1
2 3
3 1
3 2

output:

Yes
2 1
3 1
3 2
2 3
1 2
1 4

result:

wrong answer Dupped output: x,y=2,3