哇爆零了，贡献了全队93%的罚时和9%的题，我真自豪啊。

就看了五个，G不会。

J：转来转去的。我误入歧途在那里转来转去。看别人代码发现另一种很好的写法，我们可以用一个cn来保存当前转到哪了，之后直接 id+ct 就可以了。

同时发现自己写的有问题，这题和L其实差不多。

我在比赛时写的是，搜的过程中只check一条边，最后check所有的边。这样搜会有很多很多问题。。。不好描述反正这么搜不好。然后wa自闭了

看了看别人的是，先确定左上角，第一行和第一列，然后两个确定一个这样下去。

写起来不怎么难写吧，，反正不到一个小时的码量。

自己把这题想的有点复杂。

1 #include 
      
         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
       
         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
        
          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<
         
          <<' '<
          
           <
          
         
        
       
      

ILK：傻逼题。

M：很久很久之前学长讲过一毛一样的。。我看了半天代码忽然想起来。

对点排完序然后枚举长度，对于小于当前长度的点全部合并，同时合并他们的set(就是存询问),如果两个联通块里都含有同一个询问，那么答案就是当前枚举的长度。

#include 
      
       #define pii pair
       
        #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
        
          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 31 3 2 1 32 4 5 4 42 1 3 2 21 1 3 22 4 2 21 4 3 4 */