If you write on c++ you can do this:

char dot;
unsigned int x,ip;

ip = 0;

for (int i = 24; i >= 8; i -= 8) {
  cin >> x >> dot;
  x <<= i;
  ip |= x;
}
cin >> x;
ip |= x;
------------------
Now you have ip, same you can read mask.

Edited by author 21.01.2019 14:50

Edited by author 21.01.2019 14:52

To read IP address /subnet mask
I recommend you to use the following template


unsigned int read_mask(){
    unsigned int a, b, c, d;
    scanf("%u.%u.%u.%u", &a, &b, &c, &d);
    return (a<<24) + (b<<16) + (c<<8) + d;
}

my code:
WA on test 3

typedef uint32_t bitmap_t;

typedef struct {
    int val[ST_SIZE];
    int head;
} stack_t;

typedef struct {
    int V; /*vertex*/
    int *p; /*parent*/
    char *c; /*color*/
    int *d; /*distance*/
    bitmap_t *adj; /*adjacency matrix*/
} graph_t;

typedef struct {
    unsigned int ip;
    unsigned int mask;
} nic_t;

typedef struct {
    int nnic;
    nic_t nic[MAX_NIC];
} host_t;

int main(void)
{
    int i, j, c, m, n, k;
    char ip[16];
    char mask[16];
    host_t *hosts;
    graph_t *gr;
    scanf("%d", &n);
    hosts = malloc(sizeof(host_t) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &k);
        hosts[i].nnic = k;
        for (j = 0; j < k; j++) {
            scanf("%s", ip);
            scanf("%s", mask);
            hosts[i].nic[j].ip = str2ip(ip);
            hosts[i].nic[j].mask = str2ip(mask);
        }
    }
    gr = initgraph(n);
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            for (c = 0; c < hosts[i].nnic; c++) {
                for (m = 0; m < hosts[j].nnic; m++) {
                    if ((hosts[i].nic[c].ip & hosts[i].nic[c].mask) ==
                    (hosts[j].nic[m].ip & hosts[j].nic[m].mask)) {
                        setadj(gr, i, j);
                    }
                }
            }
        }
    }

    /*
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%2d", (chkadj(gr, i, j)?1:0));
        }
        printf("\n");
    }
    */

    int sp, ep;
    scanf("%d%d", &sp, &ep);
    --sp; --ep;
    bfs(gr, ep);
    if (gr->c[sp] == WHITE) {
        printf("No\n");
        exit(0);
    }
    printf("Yes\n");
    print_path(gr, sp, ep);
    printf("\n");
    return 0;
}

void bfs(graph_t *gr, int sv)
{
    if (gr->V == 0)
        return;
    int i, u, v;
    for (i = 0; i < gr->V; i++) {
        gr->c[i] = WHITE;
        gr->d[i] = INFTY;
        gr->p[i] = NPARENT;
    }
    enqueue(sv);
    gr->d[sv] = 0;
    gr->c[sv] = GREY;
    for (; dequeue(&u);) {
        for (i = 0; i < gr->V; i++) {
            if (chkadj(gr, u, i)) {
                v = i;
                if (gr->c[v] == WHITE) {
                    gr->p[v] = u;
                    gr->d[v] = gr->d[u] + 1;
                    gr->c[v] = GREY;
                    enqueue(v);
                }
            }
        }
    }
}
void print_path(graph_t *gr, int sv, int ev)
{
    printf("%d ", sv + 1);
    if (sv == ev) {
        return;
    } else {
        print_path(gr, gr->p[sv], ev);
    }
}
graph_t *initgraph(int V)
{
    graph_t *gr;
    if ((gr = malloc(sizeof(graph_t))) == NULL)
        return NULL;
    gr->V = V;
    gr->adj = initadj(gr);
    gr->p = malloc(sizeof(int) * V);
    gr->c = malloc(sizeof(int) * V);
    gr->d = malloc(sizeof(int) * V);
    if (!gr->adj || !gr->p || !gr->c || !gr->d)
        return NULL;
    return gr;
}

stack_t st_in;
stack_t st_out;

int push(stack_t *st, int val)
{
    if (st->head == ST_SIZE) {
        return ERR; /*stack full*/
    }
    st->val[st->head] = val;
    st->head++;
    return SUCC;
}
int pop(stack_t *st, int *val)
{
    if (st->head == 0) {
        return ERR;
    } else {
        st->head--;
        *val = st->val[st->head];
        return SUCC;
    }
}
int enqueue(int val)
{
    if (push(&st_in, val) == ERR) {
        return ERR;
    } else {
        return SUCC;
    }
}
int dequeue(int *val)
{
    int tmp;
    if (pop(&st_out, &tmp) == ERR) { /*empty st_out*/
        if (pop(&st_in, &tmp) == ERR) { /*empty st_in*/
            return ERR;
        } else {
            push(&st_out, tmp);
        }
        for (;;) {
            if (pop(&st_in, &tmp) == ERR) {
                break;
            } else {
                push(&st_out, tmp);
            }
        }
        pop(&st_out, val);
        return SUCC;
    } else {
        *val = tmp;
        return SUCC;
    }
}
bitmap_t *initadj(graph_t *gr)
{
    int len;
    int V = gr->V;
    len = V * V / 2 - V / 2;
    return calloc(sizeof(bitmap_t), len / INT_BIT + 1);
}
bool chkadj(graph_t *gr, int row, int col)
{
    int n = gr->V, tmp1, tmp2;
    tmp1 = row, tmp2 = col;
    row = MAX(tmp1, tmp2);
    col = MIN(tmp1, tmp2);
    return gr->adj[(row * n + col) / INT_BIT]
        & (1 << (row * n + col) % INT_BIT);
}
void setadj(graph_t *gr, int row, int col)
{
    int n = gr->V, tmp1, tmp2;
    tmp1 = row, tmp2 = col;
    row = MAX(tmp1, tmp2);
    col = MIN(tmp1, tmp2);
    gr->adj[(row * n + col) / INT_BIT] =
        gr->adj[(row * n + col) / INT_BIT]
        | (1 << (row * n + col) % INT_BIT);
}
void deladj(graph_t *gr, int row, int col)
{
    int n = gr->V, tmp1, tmp2;
    tmp1 = row, tmp2 = col;
    row = MAX(tmp1, tmp2);
    col = MIN(tmp1, tmp2);
    gr->adj[(row * n + col) / INT_BIT] =
        gr->adj[(row * n + col) / INT_BIT]
        & ~(1 << (row * n + col) % INT_BIT);
}
unsigned int str2ip(char *str)
{
    unsigned int r, b;
    for (r = 0, b = 0; *str != '\0'; str++) {
        if (*str == '.') {
            str++;
            r = r << 8;
            r += b;
            b = 0;
        }
        b = b * 10 + (*str - '0');
    }
    r = r << 8;
    r += b;
    return r;
}

what's data test 7 ???

what data test 2, because i being error wa 2

ai bít lỗi trên la gì không ? hep me!!!

Help me!, I got WA 5!.

I use dijkstra algo, what's wrong?
code



#include <cstdio>
#include <vector>
#include <map>
#include <set>
using namespace std;
const long long INF=100000000;
typedef unsigned long long ULL;
typedef pair<long long,long long> pii;
typedef vector<vector<long long> > VVI;
typedef vector<long long> vi;
typedef map<long long,vi> MIV;
MIV network;
VVI G;

long long n=1,n_int;
void init_vert(){
        for (long long i=0;i<=n;++i){
                vector< long long > temp;
                G.push_back(temp);
            }
        for (MIV::iterator it=network.begin();it!=network.end();++it){
            for(vi::iterator vit=it->second.begin();vit!=it->second.end();++vit){
                for(vi::iterator vit2=it->second.begin();vit2!=it->second.end();++vit2){
                    G[*vit].push_back(*vit2);
                }
            }
        }
    }

long long read_network(){
    long long res=0;
    long long mask=0;
    long r1,r2,r3,r4;
    long m1,m2,m3,m4;
    scanf("%ld.%ld.%ld.%ld",&r1,&r2,&r3,&r4);
    scanf("%ld.%ld.%ld.%ld",&m1,&m2,&m3,&m4);

    res+=r1&m1;res<<8;
    res+=r2&m2;res<<8;
    res+=r3&m3;res<<8;
    res+=r4&m4;

        return res;
    }


vector<long long> dist,parent;


void dejkstra(long long s){
    dist.assign(n+1,INF);
    parent.assign(n+1,INF);
    dist[s]=0;
    set<pair<long long,long long>  > q;
    q.insert(make_pair(dist[s],s));
    while (!q.empty()){
            long long v=q.begin()->second;
            q.erase(q.begin());
            for (size_t j=0;j<G[v].size();++j){
                    long long to=G[v][j];
                    if (dist[v]+1<dist[to]){
                            q.erase(make_pair(dist[to],to));
                            dist[to]=dist[v]+1;
                            parent[to]=v;
                            q.insert(make_pair(dist[to],to));
                        }
                }
        }
    }

int main(){
        //freopen("in","r",stdin);
        scanf("%lld",&n);
        long long n_n_m=0;
        for (size_t i=0;i<n;++i){
            scanf("%lld",&n_int);
            for (size_t j=0;j<n_int;++j){
                n_n_m=read_network();
                network[n_n_m].push_back(i+1);
            }
        }
        init_vert();
        long long _beg,_end;
        scanf("%lld%lld",&_beg,&_end);
        dejkstra(_beg);


        if (dist[_end]==INF){
                printf("No\n");
                return 0;
            }
        else{
                printf("Yes\n");
                long long p=_end;
                vector<long long>res;
                printf("%lld ",_beg);

                while(p!=_beg){
//                        printf(">>>%d\n",p);
                        res.push_back(p);
                        p=parent[p];


                    }
                 for (vi::reverse_iterator it=res.rbegin();it!=res.rend();++it){
                        printf("%lld ",*it);
                    }

                printf("\n");
            }
        return 0;
    }

My code...

#include <iostream>
#include <string>
using namespace std;

struct LAN
{
    int somay;
    char **IP;
    char **Sub;
};

int ChungMang(int a, int b, LAN *L);
void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq);
void Show(int dau, int cuoi, int prev[]);

void main ()
{
    int somang;
    cin>>somang;
    LAN *L;
    L= new LAN[somang+1];
    for(int i =1;i<=somang;i++)
    {
        cin>>L[i].somay;
        L[i].IP=new char*[L[i].somay];
        L[i].Sub=new char*[L[i].somay];
        for(int j = 0;j<L[i].somay;j++)
        {
            L[i].IP[j]=new char[100];
            L[i].Sub[j]=new char[100];
            cin>>L[i].IP[j]>>L[i].Sub[j];
        }
    }
    int dau, cuoi;
    cin>>dau>>cuoi;
    int d[91];
    int prev[91];
    int label[91];
    int kq=1;
    Dijkstra(L,d,prev,label,dau,cuoi,somang,kq);
    if(kq==0)
        return;
    cout<<"Yes\n";
    Show(dau,cuoi,prev);
}
void Init(int d[], int prev[], int label[], int n, int dau)
{
    for(int i=1; i<=n;i++)
    {
        d[i]=-1;
        prev[i]=-2;
        label[i]=1;
    }
    d[dau]=0;
}
void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq)
{
    Init(d,prev,label,somang,dau);
    while(label[cuoi]==1)
    {
        int iMin = -1;
        int v = -1;
        for(int i=1;i<=somang;i++)
        {
            if(label[i]==1 && d[i]!=-1&&(d[i]<iMin||iMin==-1))
            {
                iMin = d[i];
                v=i;
            }
        }
        if(iMin == -1)
        {
            cout<<"No";
            kq =0;
            break;
        }
        d[v]=iMin;
        label[v]=0;
        for(int j=1;j<=somang;j++)
        {
            if(label[j]==1&& ChungMang(v,j,L)==1)
            {
                d[j]=d[v]+1;
                prev[j]=v;
            }
        }
    }
}
int Test(char *IP3, char *IP4, char *Sub3, char *Sub4)
{
    char *IP1 = IP3;
    char *IP2=IP4;
    char *Sub1= Sub3;
    char *Sub2=Sub4;
    int i=0;
    int nIP=0;
    int nSub=0;
    while(nIP!=3)
    {
        if(IP1[i]=='.')
            nIP++;
        i++;
    }
    nIP=i;
    i=0;
    while(nSub!=3)
    {
        if(Sub1[i]=='.')
            nSub++;
        i++;
    }
    nSub=i;
    IP1[nIP]='\0';
    IP2[nIP]='\0';
    Sub1[nSub]='\0';
    Sub2[nSub]='\0';
    if(strcmp(IP1,IP2)==0&&strcmp(Sub1,Sub2)==0)
        return 1;
    return 0;
}

int ChungMang(int a, int b, LAN *L)
{
    int giong=0;
    for(int i=0;i<L[a].somay;i++)
    {
        for(int j = 0;j<L[b].somay;j++)
        {
            if(Test(L[a].IP[i],L[b].IP[j],L[a].Sub[i],L[b].Sub[j]))
                return 1;
        }
    }
    return 0;
}
void Show(int dau, int cuoi, int prev[])
{
    int temp[100];
    int i=99;
    int k = cuoi;
    cout<<dau;
    while (k != dau)
    {
        temp[i]=k;
        k=prev[k];
        i--;
    }
    for(int j = i+1;j<100;j++)
    {

            cout<<" "<<temp[j];
        cout<<endl;
    }
}

In the sample input, there is an extra space in the third line from the bottom (i.e. after the number '1'). Because there are no extra spaces in the actual tests, this extra space is better removed cuz people who use strict char by char reading (like me) might freak out fora while.

i think there are something wrong with the example:
the 6th computer:
it's ip address should be 195.38.54.65, but not 195.38.54.94.

Edited by author 08.04.2011 01:22

2
1
1.1.1.1 1.1.1.1
1
1.1.1.1 1.1.1.1
1 1

It is my program.
program sad;
var
tu:array[1..100,1..100] of int64;
d,p:array[1..1000] of int64;
f:array[1..1000] of boolean;
k,pre,pree:array[1..1000] of int64;
a:array[1..90,1..6,1..8] of int64;
ii,jj,w,i,j,m,n,u,v,bit,l,r,t,q,sum,g,i1,i2,i3,i4,n1,n2,n3,n4:longint;
c:char;s:string;

function pd:boolean;
var w:longint;
begin
for w:=1 to 4 do
if  a[i,j,w]<>a[ii,jj,w] then exit(false);
exit(true);
end;




procedure spfa(s:longint);
var i,j,k,h,t,x:longint;
begin

fillchar(f,sizeof(f),false);
fillchar(p,sizeof(p),0);
for i:=1 to n do
d[i]:=maxlongint shr 1;
f[s]:=true;
t:=1;
h:=0;
d[s]:=0;
p[t]:=s;
 while h<>t do
 begin
h:=(h mod n)+1;
x:=p[h]; f[x]:=false;
for j:=1 to n do
  if (tu[x,j]<>0) and   (d[x]+tu[x,j]<d[j])  then
  begin
  d[j]:=d[x]+tu[x,j];
  if not f[j] then
  begin
  t:=(t mod n) +1;  p[t]:=j; f[j]:=true;
  pre[j]:=x;
  end;
  end;
 end;
end;


begin
readln(n);
for i:=1 to n do
begin
readln(k[i]);
for j:=1 to k[i] do
begin
readln(s);
g:=pos('.',s);val(copy(s,1,g-1),i1);delete(s,1,g);
g:=pos('.',s);val(copy(s,1,g-1),i2);delete(s,1,g);
g:=pos('.',s);val(copy(s,1,g-1),i3);delete(s,1,g);
g:=pos(' ',s);val(copy(s,1,g-1),i4);delete(s,1,g);
g:=pos('.',s);val(copy(s,1,g-1),n1);delete(s,1,g);
g:=pos('.',s);val(copy(s,1,g-1),n2);delete(s,1,g);
g:=pos('.',s);val(copy(s,1,g-1),n3);delete(s,1,g);
val(s,n4);
a[i,j,1]:=i1 and n1;
a[i,j,2]:=i2 and n2;
a[i,j,3]:=i3 and n3;
a[i,j,4]:=i4 and n4;
end;
end;
for i:=1 to n do
for ii:=1 to n do
for j:=1 to k[i] do
for jj:=1 to k[ii] do
begin
if not pd then break;
tu[i,ii]:=1;
tu[ii,i]:=1;
end;
readln(l,r);
spfa(l);
q:=r;
sum:=0;
while q<>0 do
begin
inc(sum);
pree[sum]:=q;
q:=pre[q];
end;
if (sum>1) and (sum<>0) then begin
writeln('Yes');
for i:=sum downto 1 do
write(pree[i],' '); end else
write('No');
writeln;
end.

WA at 5# ~~
Help me~!

I think, that there was no adjustment to the "order of the computers" for output in problem "Output" paragraph. I think, that it was no difference between direct path and reverse path.
So, for example code, that printed
Yes
1 3 5 6
was Accepted, but code, that printed
Yes
6 5 3 1
was rejected.