QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#473268 | #1195. One-Way Conveyors | huangzirui | WA | 53ms | 34284kb | C++14 | 4.3kb | 2024-07-11 23:57:49 | 2024-07-11 23:57:49 |
Judging History
answer
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int maxn=200010;
int i,j,k,n,m;
map<pii,int>isCon;
vector<int>V[maxn],vNode[maxn];
int cnt,dfn[maxn],low[maxn],vis[maxn];
int Sta[maxn],tp;
int Col[maxn],cNum;
vector<int>d[maxn];
void tarjan(int now,int fa){
dfn[now]=low[now]=++cnt;
Sta[++tp]=now;vis[now]=1;
for(int x:V[now]){
if(x==fa)continue;
if(dfn[x]){
if(vis[x])
low[now]=min(low[now],low[x]);
}else{
tarjan(x,now);
low[now]=min(low[now],low[x]);
}
}
// cerr<<"tarjan now="<<now<<' '<<dfn[now]<<' '<<low[now]<<endl;
if(dfn[now]==low[now]){
++cNum;
while(Sta[tp]!=now){
Col[Sta[tp]]=cNum;
vis[Sta[tp]]=0;
d[cNum].push_back(Sta[tp--]);
}
Col[Sta[tp]]=cNum;
vis[Sta[tp]]=0;
d[cNum].push_back(Sta[tp--]);
}
}
int K;
int isGo[maxn],gNum,dep[maxn],Fa[maxn][21];
void dfs(int now,int fa){
// cerr<<"dfs "<<now<<' '<<fa<<endl;
Fa[now][0]=fa;
dep[now]=dep[fa]+1;
isGo[now]=gNum;
for(int u:vNode[now]){
if(u==fa)continue;
dfs(u,now);
}
}
void init(){
for(int i=1;i<=cNum;i++)
if(!isGo[i]){
++gNum;
dfs(i,0);
}
for(int j=1;j<=20;j++)
for(int i=1;i<=cNum;i++)
Fa[i][j]=Fa[Fa[i][j-1]][j-1];
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)
if(dep[Fa[x][i]]>=dep[y])x=Fa[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)
if(Fa[x][i]!=Fa[y][i]){
x=Fa[x][i];
y=Fa[y][i];
}
return Fa[x][0];
}
int Flag[maxn][2],sFlag[maxn][2];
void make(int x,int y){
int X=Col[x],Y=Col[y];
if(X==Y)return;
// if(isGo[x]!=isGo[y]){
// puts("No");
// exit(0);
// }
int z=lca(X,Y);
if(z==0){
puts("No");
exit(0);
}
// cerr<<"make "<<x<<" "<<y<<" | "<<X<<' '<<Y<<" -> "<<z<<endl;
Flag[X][0]++;Flag[z][0]--;
Flag[Y][1]++;Flag[z][1]--;
}
vector<pii>Ans;
map<pii,int>M;
int isWork[maxn];
void dfs2(int now,int fa){
isWork[now]=1;
for(int u:vNode[now]){
if(u==fa)continue;
dfs2(u,now);
Flag[now][0]+=Flag[u][0];
Flag[now][1]+=Flag[u][1];
}
if(Flag[now][0] && Flag[now][1]){
puts("No");
exit(0);
}
if(Flag[now][0])M[mp(now,fa)]=1,M[mp(now,fa)]=2;
else M[mp(now,fa)]=2,M[mp(now,fa)]=1;
// cerr<<now<<' '<<fa<<' '<<Flag[now][0]<<' '<<Flag[now][1]<<endl;
}
void maketree(){
for(int i=1;i<=cNum;i++)
if(!isWork[i]){
dfs2(i,0);
}
for(int i=1;i<=n;i++)
for(int j:V[i])
if(i<j && Col[i]!=Col[j]){
if(M[mp(Col[i],Col[j])]==2)Ans.push_back(mp(i,j));
else Ans.push_back(mp(j,i));
}
}
map<pii,int>Used;
int visCir[maxn],cntCir;
void dfs3(int now,int fa){
// cerr<<"dfs3 now="<<now<<' '<<fa<<endl;
visCir[now]=++cntCir;
for(int x:V[now]){
if(Col[x]==Col[now]){
if(!Used[mp(x,now)]){
Used[mp(x,now)]=Used[mp(now,x)]=1;
Ans.push_back(mp(now,x));
}
}
if(!visCir[x])dfs3(x,now);
}
}
void makeCir(){
for(int i=1;i<=n;i++)
if(!visCir[i])dfs3(i,0);
}
void getAns(){
maketree();makeCir();
puts("Yes");
for(auto x:Ans)
printf("%d %d\n",x.first,x.second);
}
int main(){
cin>>n>>m;
for(i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
V[x].push_back(y);
V[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!dfn[i])tarjan(i,0);
for(i=1;i<=n;i++)
for(int j:V[i]){
if(Col[i]==Col[j])continue;
if(isCon[mp(Col[i],Col[j])])continue;
isCon[mp(Col[i],Col[j])]=1;
isCon[mp(Col[j],Col[i])]=1;
vNode[Col[i]].push_back(Col[j]);
vNode[Col[j]].push_back(Col[i]);
}
init();
cin>>K;
for(i=1;i<=K;i++){
int x,y;
scanf("%d%d",&x,&y);
make(x,y);
}
getAns();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 27832kb
input:
3 2 1 2 2 3 3 1 2 1 3 2 3
output:
Yes 1 2 2 3
result:
ok OK!
Test #2:
score: 0
Accepted
time: 0ms
memory: 27692kb
input:
3 2 1 2 2 3 3 1 2 1 3 3 2
output:
No
result:
ok OK!
Test #3:
score: 0
Accepted
time: 5ms
memory: 27444kb
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 1 4 1 2 2 3 3 1
result:
ok OK!
Test #4:
score: 0
Accepted
time: 12ms
memory: 26076kb
input:
9990 47670 134 2450 4227 9100 1861 9948 120 8957 1161 4767 76 1714 5207 5838 2726 8974 2489 8619 2379 4933 3675 9554 344 3215 1654 6168 5630 6614 3247 5202 4456 5373 4380 6605 2626 4064 2194 6332 2749 9719 360 5059 7967 8835 5433 6494 497 6638 5945 9063 7576 7879 3550 4107 83 2891 3107 6917 2089 689...
output:
No
result:
ok OK!
Test #5:
score: 0
Accepted
time: 17ms
memory: 24340kb
input:
3219 13421 762 2133 1106 2880 2287 2476 313 992 741 1903 811 2050 1468 2184 3031 3037 403 1855 1060 1415 1792 2804 772 2956 140 2281 808 1953 895 1731 1217 1551 1264 1885 749 1082 1564 2824 1549 1741 1966 2730 112 2825 158 2625 2128 2917 128 3032 644 3194 1634 2743 1545 1961 2402 2680 2663 2814 1040...
output:
No
result:
ok OK!
Test #6:
score: 0
Accepted
time: 8ms
memory: 25724kb
input:
8013 18891 6127 6374 3969 4617 215 2699 268 6282 167 5415 1318 6256 3994 6192 4325 7186 1785 4188 6570 7153 772 5901 9 5190 873 6509 161 7476 2960 2966 4598 7170 1157 3798 758 4508 1446 5205 445 5989 686 5479 669 4711 6254 6860 1722 7020 463 3494 5063 7309 2231 6762 1208 4304 4789 5081 3925 6248 107...
output:
No
result:
ok OK!
Test #7:
score: -100
Wrong Answer
time: 53ms
memory: 34284kb
input:
9968 46595 3655 5544 5747 9340 6020 9528 5789 9882 4609 8832 1969 5167 2610 8012 324 9387 694 3647 3667 8483 4202 4963 2643 8104 1139 9679 1407 7022 9031 9944 5183 8744 3341 3858 326 2610 414 1317 657 7942 4702 5671 2072 3200 3074 3597 26 3728 288 7757 144 9580 1374 2065 2683 8068 1341 6526 2140 257...
output:
Yes 38 3 7701 5 2528 12 21 5899 5411 28 41 1675 43 2611 8563 48 2497 53 7779 64 1279 68 4366 69 2350 78 5991 79 4587 94 1435 97 2098 124 7499 126 128 3736 3731 138 139 7091 1511 148 162 5972 165 5328 7175 190 199 1169 5212 205 4113 216 4676 225 3359 239 9275 245 3134 249 8363 250 691 263 6892 269 27...
result:
wrong answer Could not reach from 7624 to 2812