哇爆零了，贡献了全队93%的罚时和9%的题，我真自豪啊。
就看了五个，G不会。
J：转来转去的。我误入歧途在那里转来转去。看别人代码发现另一种很好的写法，我们可以用一个cn来保存当前转到哪了，之后直接 id+ct 就可以了。
同时发现自己写的有问题，这题和L其实差不多。
我在比赛时写的是，搜的过程中只check一条边，最后check所有的边。这样搜会有很多很多问题。。。不好描述反正这么搜不好。然后wa自闭了
看了看别人的是，先确定左上角，第一行和第一列，然后两个确定一个这样下去。
写起来不怎么难写吧，，反正不到一个小时的码量。
自己把这题想的有点复杂。
1 #include <bits/stdc++.h>
2 using namespace std;
3 inline int read() {
4 int X=0,w=1; char c=getchar();
5 while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
6 while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
7 return X*w;
8 }
9 const int N = 3e5+5;
10 vector<int> v[N<<2];
11 int vis[N];
12 void gg(){
13 cout << "impossible" << endl;
14 exit(0);
15 }
16 int getP(int val){
17 for(auto id:v[val]){
18 if(vis[id])continue;
19 return id;
20 }
21 return -1;
22 }
23 struct Node{
24 int a[4];//a0==up
25 int nt;//nt=ind[up]
26 void init(int f,int b,int c,int d){
27 a[0]=f;a[1]=b;a[2]=c;a[3]=d;
28 }
29 int get(int num1,int num2){
30 for(int i=0;i<4;i++){
31 if(a[i]==num1&&a[(i+1)%4]==num2){
32 return i;
33 }
34 }
35 return -1;
36 }
37 }node[N];
38 vector<int> g[N];
39 int h,w;
40 void dfs_r(int ind){
41 w=ind;
42 int x=g[0][ind];
43 int num = node[x].a[(node[x].nt+3)%4];
44 if(num==0)return;
45 int nxt=getP(num);
46 if(nxt==-1)gg();
47 vis[nxt]=1;
48 int tmp=node[nxt].get(0,num);
49 if(tmp==-1)gg();
50 node[nxt].nt=tmp;
51 g[0].push_back(nxt);
52 dfs_r(ind+1);
53 }
54 void dfs_d(int ind){
55 h=ind;
56 int x=g[ind][0];
57 int num=node[x].a[(node[x].nt+2)%4];
58 if(num==0)return;
59 int nxt=getP(num);
60 if(nxt==-1)gg();
61 int tmp=node[nxt].get(num,0);
62 if(tmp==-1)gg();
63 node[nxt].nt=tmp;
64 g[ind+1].push_back(nxt);
65 vis[nxt]=1;
66 dfs_d(ind+1);
67 }
68 int n,u,lef,d,rig;
69 int main() {
70 n = read();
71 int id = -1;
72 bool f = 0;
73 for (int i = 1; i <= n; i++) {
74 u = read();lef = read();d = read();rig = read();
75 node[i].init(u, lef, d, rig);
76 int cnt = 0;
77 if (u == 0)cnt++;
78 else v[u].push_back(i);
79 if (lef == 0)cnt++;
80 else v[lef].push_back(i);
81 if (d == 0) cnt++;
82 else v[d].push_back(i);
83 if (rig == 0)cnt++;
84 else v[rig].push_back(i);
85 if (cnt>=2&&id==-1&&node[i].get(0,0)!=-1) {
86 id=i;node[i].nt=node[i].get(0,0);
87 }
88 }
89 if (id == -1)gg();
90 g[0].push_back(id);
91 vis[id]=1;
92 dfs_r(0);
93 dfs_d(0);
94 for(int i=1;i<=h;i++){
95 for(int j=1;j<=w;j++){
96 int id1=g[i-1][j];
97 int id2=g[i][j-1];
98 int num1=node[id1].a[(node[id1].nt+2)%4];
99 int num2=node[id2].a[(node[id2].nt+3)%4];
100 if(num1==0||num2==0)gg();
101 int nx1=-1,nx2=-1;
102 if(!vis[v[num1][0]])nx1=v[num1][0];
103 else if(!vis[v[num1][1]])nx1=v[num1][1];
104 if(!vis[v[num2][0]])nx2=v[num2][0];
105 else if(!vis[v[num2][1]])nx2=v[num2][1];
106 if(nx1==-1||nx2==-1)gg();
107 if(nx1!=nx2)gg();
108 int tmp = node[nx1].get(num1,num2);
109 if(tmp==-1)gg();
110 node[nx1].nt=tmp;
111 g[i].push_back(nx1);
112 vis[nx2]=1;
113 if(i==h)if(node[nx1].a[(node[nx1].nt+2)%4])gg();
114 if(j==w)if(node[nx1].a[(node[nx1].nt+3)%4])gg();
115
116 }
117 }
118 if((h+1)*(w+1)!=n)gg();
119 if(h==0){
120 for(int i=0;i<=w;i++){
121 int id=g[0][i];
122 int cn=node[id].nt;
123 if(node[id].a[(cn+2)%4])gg();
124 if(i==w&&node[id].a[(cn+3)%4])gg();
125 }
126 }
127 if(w==0){
128 for(int i=0;i<=h;i++){
129 int id=g[i][0];
130 int cn=node[id].nt;
131 if(node[id].a[(cn+3)%4])gg();
132 if(i==h&&node[id].a[(cn+2)%4])gg();
133 }
134 }
135 cout<<h+1<<' '<<w+1<<endl;
136 for(int i=0;i<=h;i++){
137 for(int j=0;j<=w;j++)
138 cout<<g[i][j]<<' ';
139 cout<<endl;
140 }
141 }
142 /**
143 6
144 0 0 1 6
145 0 7 4 0
146 0 0 2 1
147 5 3 0 6
148 3 7 0 0
149 4 5 2 0
150 */
View Code
ILK：傻逼题。
M：很久很久之前学长讲过一毛一样的。。我看了半天代码忽然想起来。
对点排完序然后枚举长度，对于小于当前长度的点全部合并，同时合并他们的set(就是存询问),如果两个联通块里都含有同一个询问，那么答案就是当前枚举的长度。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
const int N = 502;
int a[N][N],fa[N<<9],ans[N<<9];
bool vis[N<<9];
set<int> g[N<<9];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
pii b[N<<9];
int fx[]={-1,0,1,0};
int fy[]={0,-1,0,1};
int n,m,q;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
fa[(i-1)*m+j]=(i-1)*m+j;
b[(i-1)*m+j]=mk(a[i][j],(i-1)*m+j);
}
}
int x1,y1,x2,y2,cnt=n*m;
for(int i=1;i<=q;i++){
cin>>x1>>y1>>x2>>y2;
if(x1==x2&&y1==y2){
ans[i]=a[x1][y1];
} else{
g[(x1-1)*m+y1].insert(i);
g[(x2-1)*m+y2].insert(i);
}
}
sort(b+1,b+cnt+1);//
for(int i=1;i<=cnt;i++){
pii t = b[i];
vis[t.second]=1;
int x=(t.second-1)/m+1,y=(t.second-1)%m+1;
for(int j=0;j<4;j++){
int nx=x+fx[j],ny=y+fy[j];
if(nx<1||nx>n||ny<1||ny>m||!vis[(nx-1)*m+ny])continue;
int u=find((x-1)*m+y),v=find((nx-1)*m+ny);
if(u==v)continue;
if(g[u].size()>g[v].size())swap(u,v);
fa[u]=v;
for(auto e:g[u]){
if(g[v].count(e))
ans[e]=t.first,g[v].erase(e);
else g[v].insert(e);
}
}
}
for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
return 0;
}
/**
3 5 3
1 3 2 1 3
2 4 5 4 4
2 1 3 2 2
1 1 3 2
2 4 2 2
1 4 3 4
*/
View Code