Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

原来memset有增大内存的效果:

Posted by xxww at 2011-03-05 17:09:22 on Problem 3177 and last updated at 2011-03-05 17:13:42
一开始内存为1060k,用了memset后瞬间变为24000+k
神奇呀

#include <cstdio>
#include <cstring>
#define min(a,b)(a<b?a:b)
#define N 10010
#define M 20010
int n, m, dfn[N]= {0}, low[N], h[N], e[M], ne[M], idx, t, num, time ;
bool map[20000][20000] = {0};
void add (int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
}
int tarjan (int u, int v)
{
    int i, s = 0 ;
    dfn[u] = low[u] = ++ time ;
    for (i = h[u]; i != -1; i = ne[i])
        if (!dfn[e[i]]){
            t = tarjan (e[i], u) ;
            low[u] = min(low[u], low[e[i]]) ;
            if (low[e[i]] > dfn[u]) num += !t, s ++ ;
            else s += t ;}
        else if (e[i] != v && dfn[e[i]] < dfn[u]) low[u] = min(low[u], dfn[e[i]]) ;
    return s ;
}
int main ()
{
    int i, j ;
    scanf ("%d%d", &n, &m) ;
    idx = num = time = 0 ;
    memset (h, -1, sizeof h) ;
    memset (map, 0, sizeof map) ;
    while (m -- ){
        scanf ("%d%d", &i, &j) ;
        if (!map[i][j]){
            add (i, j) ;
            add (j, i) ;
            map[i][j] = map[j][i] = 1 ;}}
    num += tarjan (1, -1) == 1 ;
    printf ("%d\n", (num + 1) >> 1) ;
    return 0 ;
}

大家快看呀, 我开了一个381MB的数组,居然status里却写着1000+k

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator