提出 #34083578 - AtCoder Regular Contest 092

コンテスト時間: 2018-03-17 21:00:00+0900 ~ 2018-03-17 22:40:00+0900 (100分) AtCoderホームへ戻る

提出 #34083578

ソースコード拡げる

#include <cstdio>
#include <cstring>
#include <queue>

const int MAXN = 1e3;
const int MAXM = 2e5;

int n, m;
int vis[MAXN + 10], pre1[MAXN + 10], pre2[MAXN + 10];
int get[MAXN + 10][MAXN + 10];
bool ans[MAXN + 10][MAXN + 10], sgn[MAXN + 10], chk[MAXN + 10];

int head[MAXN + 10], numEdge;
struct Edge {
    int nxt, to;
}edge[MAXM + 10];

void addEdge(int x, int y) {
    ++numEdge;
    edge[numEdge].nxt = head[x];
    edge[numEdge].to = y;
    head[x] = numEdge;
}

void dfs(int u, int rt) {

    vis[u] = 1;
    for(int i = head[u]; i; i = edge[i].nxt) {
        int k = edge[i].to;
        if(!vis[k]) {
            get[rt][k] = true;
            dfs(k, rt);
        }
    }

    return;
}

std::queue<int>que;
std::vector<std::pair<int, int> >vec;
int main() {

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        addEdge(x, y);
        vec.push_back(std::make_pair(x, y));
    }
    for(int i = 1; i <= n; ++i) {
        std::memset(vis, 0, sizeof(vis));
        dfs(i, i);
    }
    
    for(int u = 1; u <= n; ++u) {
        std::memset(vis, 0, sizeof(vis));
        std::memset(sgn, false, sizeof(sgn));
        std::memset(chk, false, sizeof(chk));
        std::memset(pre1, 0, sizeof(pre1));
        std::memset(pre2, 0, sizeof(pre2));
        while(!que.empty()) {
            que.pop();
        }
        for(int i = head[u]; i; i = edge[i].nxt) {
            int k = edge[i].to;
            que.push(k);
            sgn[k] = true;
            pre1[k] = k;
        }
        while(!que.empty()) {
            int nw = que.front();
            que.pop();
            for(int i = head[nw]; i; i = edge[i].nxt) {
                int k = edge[i].to;
                if(k == u || (pre1[k] == pre1[nw] && !pre2[nw]))
                    continue;
                ++vis[k];
                if(sgn[k] && (pre2[nw] || pre1[nw] != k)) {
                    chk[k] = true;
                    if(!pre2[k]) {
                        pre2[k] = (pre1[nw] != k ? pre1[nw] : pre2[nw]);
                    }
                }
                else {
                    if(!pre1[k]) {
                        pre1[k] = pre1[nw];
                        pre2[k] = pre2[nw];
                    }
                    else if(!pre2[k]) {
                        pre2[k] = (pre1[nw] != pre1[k] ? pre1[nw] : pre2[nw]);
                    }
                }
                if(vis[k] <= 2) {
                    que.push(k);
                }
            }
        }
        for(int i = head[u]; i; i = edge[i].nxt) {
            int k = edge[i].to;
            if(chk[k]) {
                ans[u][k] = true;
            }
        }
    }

    for(auto &k : vec) {
        puts(ans[k.first][k.second] && !get[k.second][k.first] || !ans[k.first][k.second] && get[k.second][k.first] ? "diff" : "same");
    }

    return 0;
}

提出情報

提出日時	2022-08-16 15:44:45+0900
問題	F - Two Faced Edges
ユーザ	louis_660
言語	C++ (Clang 10.0.0)
得点	0
コード長	2994 Byte
結果	TLE
実行時間	5513 ms
メモリ	11108 KiB

コンパイルエラー

./Main.cpp:107:37: warning: '&&' within '||' [-Wlogical-op-parentheses]
        puts(ans[k.first][k.second] && !get[k.second][k.first] || !ans[k.first][k.second] && get[k.second][k.first] ? "diff" : "same");
             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~ ~~
./Main.cpp:107:37: note: place parentheses around the '&&' expression to silence this warning
        puts(ans[k.first][k.second] && !get[k.second][k.first] || !ans[k.first][k.second] && get[k.second][k.first] ? "diff" : "same");
                                    ^
             (                                                )
./Main.cpp:107:91: warning: '&&' within '||' [-Wlogical-op-parentheses]
        puts(ans[k.first][k.second] && !get[k.second][k.first] || !ans[k.first][k.second] && get[k.second][k.first] ? "diff" : "same");
                                                               ~~ ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:107:91: note: place parentheses around the '&&' expression to silence this warning
        puts(ans[k.first][k.second] && !get[k.second][k.first] || !ans[k.first][k.second] && get[k.second][k.first] ? "diff" : "same");
                                                                                          ^
                                                                  (                                                )
2 warnings generated.

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

0 / 1100

結果

× 3

AC	× 36
TLE	× 19

セット名	テストケース
Sample	example_0, example_1, example_2
All	bigcycle_0, bigcycle_1, dag_0, dag_1, dag_2, dag_3, dag_4, dag_5, dag_6, dag_7, dagex2_0, dagex2_1, dagex2_2, dagex2_3, dagex_0, dagex_1, dagex_2, dagex_3, example_0, example_1, example_2, maxrand_0, maxrand_1, sep2_0, sep2_1, sep2ex_0, sep2ex_1, sep2ex_2, sep2ex_3, sep2ex_4, sep2ex_5, sep2ex_6, sep2ex_7, sep2ex_8, sep2ex_9, smallrand_0, smallrand_1, smallrand_2, smallrand_3, smallrand_4, smallrand_5, smallrand_6, smallrand_7, smallrand_8, smallrand_9, sparserand_0, sparserand_1, worst2_0, worst2_1, worst2_2, worst2_3, worst_0, worst_1, worst_2, worst_3

ケース名	結果	実行時間	メモリ
bigcycle_0	TLE	5513 ms	10500 KiB
bigcycle_1	TLE	5513 ms	10360 KiB
dag_0	AC	1128 ms	9416 KiB
dag_1	AC	4440 ms	10748 KiB
dag_2	AC	2479 ms	9316 KiB
dag_3	TLE	5513 ms	10512 KiB
dag_4	AC	3551 ms	10708 KiB
dag_5	AC	4402 ms	10796 KiB
dag_6	TLE	5513 ms	10184 KiB
dag_7	TLE	5513 ms	10516 KiB
dagex2_0	AC	3714 ms	10488 KiB
dagex2_1	AC	4446 ms	10880 KiB
dagex2_2	AC	3908 ms	10712 KiB
dagex2_3	AC	4468 ms	10912 KiB
dagex_0	AC	3386 ms	10596 KiB
dagex_1	AC	4492 ms	10824 KiB
dagex_2	AC	2871 ms	10212 KiB
dagex_3	AC	4559 ms	10752 KiB
example_0	AC	7 ms	2968 KiB
example_1	AC	3 ms	3160 KiB
example_2	AC	2 ms	2984 KiB
maxrand_0	TLE	5513 ms	10480 KiB
maxrand_1	TLE	5513 ms	10456 KiB
sep2_0	TLE	5513 ms	10444 KiB
sep2_1	TLE	5513 ms	10440 KiB
sep2ex_0	TLE	5513 ms	10972 KiB
sep2ex_1	TLE	5513 ms	10860 KiB
sep2ex_2	TLE	5513 ms	11100 KiB
sep2ex_3	TLE	5513 ms	11108 KiB
sep2ex_4	TLE	5513 ms	10888 KiB
sep2ex_5	TLE	5513 ms	10788 KiB
sep2ex_6	TLE	5513 ms	10592 KiB
sep2ex_7	TLE	5513 ms	10448 KiB
sep2ex_8	TLE	5513 ms	10400 KiB
sep2ex_9	TLE	5513 ms	10500 KiB
smallrand_0	AC	9 ms	3068 KiB
smallrand_1	AC	2 ms	3132 KiB
smallrand_2	AC	2 ms	3072 KiB
smallrand_3	AC	2 ms	3044 KiB
smallrand_4	AC	2 ms	3216 KiB
smallrand_5	AC	1 ms	3252 KiB
smallrand_6	AC	3 ms	2976 KiB
smallrand_7	AC	2 ms	3084 KiB
smallrand_8	AC	2 ms	2940 KiB
smallrand_9	AC	5 ms	3196 KiB
sparserand_0	AC	245 ms	8084 KiB
sparserand_1	AC	244 ms	8056 KiB
worst2_0	AC	54 ms	8140 KiB
worst2_1	AC	298 ms	9180 KiB
worst2_2	AC	54 ms	8640 KiB
worst2_3	AC	223 ms	9748 KiB
worst_0	AC	3460 ms	10612 KiB
worst_1	AC	4355 ms	10640 KiB
worst_2	AC	846 ms	10196 KiB
worst_3	AC	1464 ms	10620 KiB