oj.uz

Submission #41688

# Submission time Handle Problem Language Result Execution time Memory
41688 2018-02-20T16:52:25 Z octopuses Potemkin cycle (CEOI15_indcyc) C++14
10 / 100
 1000 ms 32012 KB 
//Giorgi Kldiashvili

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define M 1000000007ll
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)

using namespace std;
const int N = 1020;

ull pw[64], mm;
int n, m;
int A[N][N], P[100020], p[100020];
bool used[100020];
vector < int > G[N], g[100020];
pair < int, int > a[100020], id[N];
ull non[N][16], d[16];

int f(int x, int y)
{
  if(a[x].first == a[y].first || a[x].first == a[y].second)
    return a[x].first + 1;
  return a[x].second + 1;
}

void go(int v)
{
  used[v] = true;
  for(int i = 0; i < g[v].size(); ++ i)
  {
    int to = g[v][i];
    if(to == p[v])
      continue;
    if(used[to])
    {
      p[to] = v;
      int now = v;
      printf("%d ", f(now, p[now]));
      while(now != to)
      {
        now = p[now];
        printf("%d ", f(now, p[now]));
      }
      exit(0);
    }
    p[to] = v;
    go(to);
  }
}

void finish(int x)
{
  go(x);
}

int Parent(int x)
{
  if(P[x] == x)
    return x;
  return P[x] = Parent(P[x]);
}

void DSU(int x, int y)
{
  g[x].push_back(y);
  g[y].push_back(x);
  x = Parent(x);
  y = Parent(y);
  if(x == y)
    finish(x);
  P[x] = y;
}

int main()
{
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);

  pw[0] = 1;
  mm = 1;
  for(int i = 1; i < 64; ++ i)
  {
    pw[i] = pw[i - 1] * 2;
    mm += pw[i];
  }

  scanf("%d %d", &n, &m);

  for(int i = 1; i <= m; ++ i)
  {
    P[i] = i;
    scanf("%d %d", &a[i].first, &a[i].second);
    int x = -- a[i].first;
    int y = -- a[i].second;
    A[x][y] = A[y][x] = i;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  for(int i = 0; i < n; ++ i)
    id[i] = {i / 64, i % 64};
  for(int i = 0; i < n; ++ i)
  {
    for(int j = 0; j < 16; ++ j)
      non[i][j] = mm;
    for(int j = 0; j < n; ++ j)
      if(A[i][j])
        non[i][id[j].first] ^= pw[id[j].second];
  }

  for(int v = 0; v < n; ++ v)
  {
    for(int j = 0; j < 16; ++ j)
      d[j] = 0;
    for(int j = 0; j < G[v].size(); ++ j)
    {
      int u = G[v][j];
      for(int i = 0; i < 16; ++ i)
      {
        int x = d[i] & non[u][i];
        if(!x) continue;
        for(int y = 0; y < 64; ++ y)
        {
          if(!(x & pw[y])) continue;
          DSU(A[v][u], A[v][i * 64 + y]);
        }
      }
      d[id[u].first] ^= pw[id[u].second];
    }
  }
  printf("no");
}

Compilation message

indcyc.cpp: In function 'void go(int)':
indcyc.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < g[v].size(); ++ i)
                    ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:117:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < G[v].size(); ++ j)
                      ^
indcyc.cpp:90:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
                         ^
indcyc.cpp:95:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a[i].first, &a[i].second);
                                              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 3 ms 2896 KB Output is correct
4 Correct 3 ms 2896 KB Output is correct
5 Correct 4 ms 2896 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3028 KB Repeated vertex

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3112 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3500 KB Repeated vertex

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3504 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4380 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4448 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 8712 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 32012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 32012 KB Repeated vertex
2 Halted 0 ms 0 KB -