Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

同崩溃中 ~~挖了20多` `TLE 几次` MLE 8次 ``RE 10来次

Posted by 01ly at 2008-07-27 18:10:25 on Problem 3678

同崩溃中
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 3000
#define MAX_LOP 1000

int t[MAX_SIZE][MAX_SIZE];
int p[MAX_LOP][MAX_SIZE];
int q[1000000];
int f, l;
int m, n;
int flag;
int po;
int Solve(int ind)
{
    
    if(flag == 1)
        return 1;
    while(l < f)
    {
        if(flag < 0)
            break;
        int pos = q[l++];
        for(int i = 0; i < n && !flag; ++i)
        {
            if(t[pos][i] <= 0)
                continue;
            if(t[pos][i] == 1)
            {
                if(p[ind][i] < 0 && !p[ind][pos])
                {
                    p[ind][i] = 1;
                    q[f++] = i;
                    continue;
                }
                if(!p[ind][pos] && !p[ind][i])
                {    
                     return -1;
                }
                continue;
            }
            if(t[pos][i] == 2)
            {
                if(p[ind][i] < 0 && p[ind][pos] == 1)
                {
                    p[ind][i] = 0;
                    q[f++] = i;
                    continue;
                }
                if(p[ind][pos] == 1 && p[ind][i] == 1)
                {
                    return -1;
                }
                continue;
            }
            if(t[pos][i] == 3)
            {
                if(p[ind][i] < 0)
                {
                    q[f++] = i;
                    if(p[ind][pos] == 1)
                        p[ind][i] = 0;
                    else
                        p[ind][i] = 1;
                }
                else
                {
                    if(!p[ind][i] && !p[ind][pos])
                        return -1;
                    else if(p[ind][i] == 1 && p[ind][pos] == 1)
                        return -1;
                }
                continue;
            }
            if(t[pos][i] == 4)
            {
                if(p[ind][i] < 0)
                {
                    q[f++] = i;
                    if(p[ind][pos] == 1)
                        p[ind][i] = 1;
                    else
                        p[ind][i] = 0;
                }
                else
                {
                    if(!p[ind][i] && p[ind][pos] == 1)
                        return -1;
                    else if(p[ind][i] == 1 && !p[ind][pos])
                        return -1;
                }
                continue;
            }
        }
    }
    for(int i = 0; i < n; ++i)
    {
        if(p[ind][i] < 0)
        {
            for(int j = 0; j < n; ++j)
                p[ind+1][j] = p[ind][j];
            p[ind+1][i] = 1;
            q[0] = i;
            l = 0;
            f = 1;
            int res = Solve(ind+1);
            if(res == 1)
            {   
                flag = 1;
                return 1;
            }
            for(int j = 0; j < n; ++j)
                p[ind+1][j] = p[ind][j];
            p[ind+1][i] = 1;
            q[0] = i;
            l = 0;
            f = 1;
            res = Solve(ind+1);
            if(res == 1)
            {   
                flag = 1;
                return 1;
            }
        }
    }
    
    return 1;
    //for(int i = 0; i < n; ++i)
    //{
        //for(int j = 0; j < n; ++j)
            //printf("%d ", t[i][j]);
        //printf("\n");
    //}
    //for(int i = 0; i < n; ++i)
        //printf("%d ", p[i]);
    //printf("\n");
    
}
            
                
                    
                         
            
int main( )
{
    scanf("%d %d", &n, &m);
    memset(p, 0xff, sizeof(p[0]) );
    while(m--)
    {
        int a, b, c;
        char s[10];
        scanf("%d %d %d %s", &a, &b, &c, s);
        if(c && s[0] == 'A')
        {
            if(!p[0][a] || !p[0][b])
                flag = -1;
            if(p[0][a] < 0)
               q[f++] = a;
            p[0][a] = 1;
            if(p[0][b] < 0)
               q[f++] = b;
            p[0][b] = 1;
            t[a][b] = -1;
            t[b][a] = -1;
            continue;
        }
        if(!c && s[0] == 'O')
        {
            if(p[0][a] == 1 || p[0][b] == 1)
                flag = -1;
            if(p[0][a] < 0)
               q[f++] = a;
            p[0][a] = 0;
            if(p[0][b] < 0)
               q[f++] = b;
            p[0][b] = 0;
            t[a][b] = -1;
            t[b][a] = -1;
            continue;
        }
        if(c && s[0] == 'O')
        {    
            t[a][b] = 1;
            t[b][a] = 1;
            continue;
        }
        if(!c && s[0] == 'A')
        {
            t[a][b] = 2;
            t[b][a] = 2;
            continue;
        } 
        if(c && s[0] == 'X')
        {
            t[a][b] = 3;
            t[b][a] = 3;
            continue;
        }
        if(!c && s[0] == 'X')
        {
            t[b][a] = 4;
            t[a][b] = 4;
            continue;
        }
    }
    if(flag < 0)
        printf("NO\n");
    else
    {
        Solve(0);
        //for(int i = 0; i < n; ++i)
            //printf("%d ", p[0][i]);
        //printf("\n");
        if(flag < 0)
            printf("NO\n");
        else
            printf("YES\n");
    }
    
    //system("pause");
    return 0;
}

Followed by:

Re:传说中的分母…… (46) qq512572354 2010-08-03 13:39:05

Post your reply here:

User ID:
Password:
Title:

Content:

> 同崩溃中
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> 
> #define MAX_SIZE 3000
> #define MAX_LOP 1000
> 
> int t[MAX_SIZE][MAX_SIZE];
> int p[MAX_LOP][MAX_SIZE];
> int q[1000000];
> int f, l;
> int m, n;
> int flag;
> int po;
> int Solve(int ind)
> {
>     
>     if(flag == 1)
>         return 1;
>     while(l < f)
>     {
>         if(flag < 0)
>             break;
>         int pos = q[l++];
>         for(int i = 0; i < n && !flag; ++i)
>         {
>             if(t[pos][i] <= 0)
>                 continue;
>             if(t[pos][i] == 1)
>             {
>                 if(p[ind][i] < 0 && !p[ind][pos])
>                 {
>                     p[ind][i] = 1;
>                     q[f++] = i;
>                     continue;
>                 }
>                 if(!p[ind][pos] && !p[ind][i])
>                 {    
>                      return -1;
>                 }
>                 continue;
>             }
>             if(t[pos][i] == 2)
>             {
>                 if(p[ind][i] < 0 && p[ind][pos] == 1)
>                 {
>                     p[ind][i] = 0;
>                     q[f++] = i;
>                     continue;
>                 }
>                 if(p[ind][pos] == 1 && p[ind][i] == 1)
>                 {
>                     return -1;
>                 }
>                 continue;
>             }
>             if(t[pos][i] == 3)
>             {
>                 if(p[ind][i] < 0)
>                 {
>                     q[f++] = i;
>                     if(p[ind][pos] == 1)
>                         p[ind][i] = 0;
>                     else
>                         p[ind][i] = 1;
>                 }
>                 else
>                 {
>                     if(!p[ind][i] && !p[ind][pos])
>                         return -1;
>                     else if(p[ind][i] == 1 && p[ind][pos] == 1)
>                         return -1;
>                 }
>                 continue;
>             }
>             if(t[pos][i] == 4)
>             {
>                 if(p[ind][i] < 0)
>                 {
>                     q[f++] = i;
>                     if(p[ind][pos] == 1)
>                         p[ind][i] = 1;
>                     else
>                         p[ind][i] = 0;
>                 }
>                 else
>                 {
>                     if(!p[ind][i] && p[ind][pos] == 1)
>                         return -1;
>                     else if(p[ind][i] == 1 && !p[ind][pos])
>                         return -1;
>                 }
>                 continue;
>             }
>         }
>     }
>     for(int i = 0; i < n; ++i)
>     {
>         if(p[ind][i] < 0)
>         {
>             for(int j = 0; j < n; ++j)
>                 p[ind+1][j] = p[ind][j];
>             p[ind+1][i] = 1;
>             q[0] = i;
>             l = 0;
>             f = 1;
>             int res = Solve(ind+1);
>             if(res == 1)
>             {   
>                 flag = 1;
>                 return 1;
>             }
>             for(int j = 0; j < n; ++j)
>                 p[ind+1][j] = p[ind][j];
>             p[ind+1][i] = 1;
>             q[0] = i;
>             l = 0;
>             f = 1;
>             res = Solve(ind+1);
>             if(res == 1)
>             {   
>                 flag = 1;
>                 return 1;
>             }
>         }
>     }
>     
>     return 1;
>     //for(int i = 0; i < n; ++i)
>     //{
>         //for(int j = 0; j < n; ++j)
>             //printf("%d ", t[i][j]);
>         //printf("\n");
>     //}
>     //for(int i = 0; i < n; ++i)
>         //printf("%d ", p[i]);
>     //printf("\n");
>     
> }
>             
>                 
>                     
>                          
>             
> int main( )
> {
>     scanf("%d %d", &n, &m);
>     memset(p, 0xff, sizeof(p[0]) );
>     while(m--)
>     {
>         int a, b, c;
>         char s[10];
>         scanf("%d %d %d %s", &a, &b, &c, s);
>         if(c && s[0] == 'A')
>         {
>             if(!p[0][a] || !p[0][b])
>                 flag = -1;
>             if(p[0][a] < 0)
>                q[f++] = a;
>             p[0][a] = 1;
>             if(p[0][b] < 0)
>                q[f++] = b;
>             p[0][b] = 1;
>             t[a][b] = -1;
>             t[b][a] = -1;
>             continue;
>         }
>         if(!c && s[0] == 'O')
>         {
>             if(p[0][a] == 1 || p[0][b] == 1)
>                 flag = -1;
>             if(p[0][a] < 0)
>                q[f++] = a;
>             p[0][a] = 0;
>             if(p[0][b] < 0)
>                q[f++] = b;
>             p[0][b] = 0;
>             t[a][b] = -1;
>             t[b][a] = -1;
>             continue;
>         }
>         if(c && s[0] == 'O')
>         {    
>             t[a][b] = 1;
>             t[b][a] = 1;
>             continue;
>         }
>         if(!c && s[0] == 'A')
>         {
>             t[a][b] = 2;
>             t[b][a] = 2;
>             continue;
>         } 
>         if(c && s[0] == 'X')
>         {
>             t[a][b] = 3;
>             t[b][a] = 3;
>             continue;
>         }
>         if(!c && s[0] == 'X')
>         {
>             t[b][a] = 4;
>             t[a][b] = 4;
>             continue;
>         }
>     }
>     if(flag < 0)
>         printf("NO\n");
>     else
>     {
>         Solve(0);
>         //for(int i = 0; i < n; ++i)
>             //printf("%d ", p[0][i]);
>         //printf("\n");
>         if(flag < 0)
>             printf("NO\n");
>         else
>             printf("YES\n");
>     }
>     
>     //system("pause");
>     return 0;
> }
>         
>

Home Page Go Back To top