QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#131355 | #1195. One-Way Conveyors | KLPP# | WA | 5ms | 30128kb | C++20 | 4.9kb | 2023-07-27 00:02:55 | 2023-07-27 00:02:59 |
Judging History
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