oj.uz

답안 #314927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314927 2020-10-21T16:18:37 Z mohamedsobhi777 Pipes (CEOI15_pipes) C++14
0 / 100
 5000 ms 12416 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;

// How interesting!

int n, m, t;
vector<int> adj[N];
int low[N], tim[N];

void dfs(int x, int p)
{
        low[x] = tim[x] = ++t;
        for (auto u : adj[x])
        {
                if (u == p)
                        continue;
                if (low[u])
                {
                        low[x] = min(low[x], tim[u]);
                }
                else
                {
                        dfs(u, x);
                        low[x] = min(low[x], low[u]);
                }
                if (low[u] > tim[x])
                {
                        cout << x << " " << u << "\n";
                }
        }
}

struct dsu
{
        int fat[N];
        dsu()
        {
                for (int i = 0; i < N; ++i)
                        fat[i] = i;
        }
        int find(int x) { return (x == fat[x] ? x : find(fat[x])); }

        void link(int u, int v)
        {
                u = find(u);
                v = find(v);
                if (u != v)
                {
                        fat[u] = v;
                }
        }

        bool same(int u, int v)
        {
                return find(u) == find(v);
        }
} d1, d2;

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> m;
        for (int i = 0; i < m; ++i)
        {
                int u, v;
                cin >> u >> v;
                if (!d1.same(u, v))
                {
                        d1.link(u, v);
                }
                else if (!d2.same(u, v))
                {
                        d2.link(u, v);
                }
                else
                        continue;
                adj[u].push_back(v);
                adj[v].push_back(u);
        }
        for (int i = 1; i <= n; ++i)
        {
                if (!low[i])
                        dfs(i, i);
        }

        return 0;
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6656 KB Output is correct
2 Incorrect 5 ms 6656 KB Wrong number of edges

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 7160 KB Output is correct
2 Incorrect 16 ms 6912 KB Wrong number of edges

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2980 ms 12416 KB Output is correct
2 Incorrect 591 ms 12152 KB Wrong number of edges

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5044 ms 9544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5099 ms 8920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5055 ms 10676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5069 ms 10872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5045 ms 11280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5005 ms 11356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5042 ms 11208 KB Time limit exceeded
2 Halted 0 ms 0 KB -