oj.uz

답안 #22986

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22986 2017-05-01T02:39:30 Z model_code Network (BOI15_net) C++11
18 / 100
 2000 ms 14364 KB 
/*/
  Task: net
  Brute-force solution
  Without early termination
  With O(n^2) bridge finding
  Author: Bartosz Kostka 
/*/

#include "bits/stdc++.h"

using namespace std;

const int MAXN = 500007;

vector <int> L, G[MAXN];
vector <int> S;
int w, n;

int licz;
bool vis[MAXN];

void dfs(int v)
{
  vis[v] = true;
  for(auto w : G[v])
    if(vis[w]==false)
       dfs(w);
}

bool bridges()
{
  for(int i=1; i<=n; i++)
    for(int j=0; j<(int)G[i].size(); j++)
    {
      int c = G[i][j];
      swap(G[i][j], G[i].back());
      G[i].pop_back();
      for(int k=1; k<=n; k++)
        vis[k] = false;
      dfs(1);
      G[i].push_back(c);
      swap(G[i][j], G[i].back());
      for(int k=1; k<=n; k++)
        if(!vis[k])
          return true;
    }
  return false;
}


void go(vector <int> &L, vector <int> &A)
{
  if(L.size() <= 1)
  {
    if(!L.empty())
    {
      G[L[0]].push_back(w);
      G[w].push_back(L[0]);
      A.push_back(L[0]);
      A.push_back(w);
      if(bridges()==false)
        S = A;
      A.pop_back();
      A.pop_back();
      G[w].pop_back();
      G[L[0]].pop_back();
    }
    else
    {
      if(bridges()==false)
        S = A;
    }
    return;
  }
  int a = L.back();
  L.pop_back();
  int ls = (int)L.size();
  A.push_back(a);
  for(int i=0; i<ls; i++)
  {
    swap(L[i], L.back());
    int b = L.back();
    L.pop_back();

    G[a].push_back(b);
    G[b].push_back(a);
    A.push_back(b);

    go(L,A);

    A.pop_back();
    G[b].pop_back();
    G[a].pop_back();
    
    L.push_back(b);
    swap(L[i], L.back());
  }
  A.pop_back();
  L.push_back(a);
}

int main()
{
  scanf("%d", &n);
  for(int i=1; i<n; i++)
  {
    int a, b;
    scanf("%d%d", &a, &b);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  for(int i=1; i<=n; i++)
  {
    if((int)G[i].size() == 1)
      L.push_back(i);
    else
      w = i;
  }
  vector <int> AA;
  go(L,AA);
  printf("%d\n", (int)S.size()/2);
  for(int i=0; i<(int)S.size(); i+=2)
    printf("%d %d\n", S[i], S[i+1]);
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:104:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
net.cpp:108:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &a, &b);
                          ^

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14232 KB Output is correct
2 Correct 3 ms 14232 KB Output is correct
3 Correct 6 ms 14232 KB Output is correct
4 Correct 0 ms 14232 KB Output is correct
5 Correct 0 ms 14232 KB Output is correct
6 Correct 0 ms 14232 KB Output is correct
7 Correct 0 ms 14232 KB Output is correct
8 Correct 0 ms 14232 KB Output is correct
9 Correct 0 ms 14232 KB Output is correct
10 Correct 3 ms 14232 KB Output is correct
11 Correct 3 ms 14232 KB Output is correct
12 Correct 0 ms 14232 KB Output is correct
13 Correct 0 ms 14232 KB Output is correct
14 Correct 0 ms 14232 KB Output is correct
15 Correct 3 ms 14232 KB Output is correct
16 Correct 6 ms 14232 KB Output is correct
17 Correct 6 ms 14232 KB Output is correct
18 Correct 0 ms 14232 KB Output is correct
19 Correct 3 ms 14232 KB Output is correct
20 Correct 0 ms 14232 KB Output is correct

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14232 KB Output is correct
2 Correct 3 ms 14232 KB Output is correct
3 Correct 6 ms 14232 KB Output is correct
4 Correct 0 ms 14232 KB Output is correct
5 Correct 0 ms 14232 KB Output is correct
6 Correct 0 ms 14232 KB Output is correct
7 Correct 0 ms 14232 KB Output is correct
8 Correct 0 ms 14232 KB Output is correct
9 Correct 0 ms 14232 KB Output is correct
10 Correct 3 ms 14232 KB Output is correct
11 Correct 3 ms 14232 KB Output is correct
12 Correct 0 ms 14232 KB Output is correct
13 Correct 0 ms 14232 KB Output is correct
14 Correct 0 ms 14232 KB Output is correct
15 Correct 3 ms 14232 KB Output is correct
16 Correct 6 ms 14232 KB Output is correct
17 Correct 6 ms 14232 KB Output is correct
18 Correct 0 ms 14232 KB Output is correct
19 Correct 3 ms 14232 KB Output is correct
20 Correct 0 ms 14232 KB Output is correct
21 Correct 0 ms 14232 KB Output is correct
22 Execution timed out 2000 ms 14364 KB Execution timed out
23 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14232 KB Output is correct
2 Correct 3 ms 14232 KB Output is correct
3 Correct 6 ms 14232 KB Output is correct
4 Correct 0 ms 14232 KB Output is correct
5 Correct 0 ms 14232 KB Output is correct
6 Correct 0 ms 14232 KB Output is correct
7 Correct 0 ms 14232 KB Output is correct
8 Correct 0 ms 14232 KB Output is correct
9 Correct 0 ms 14232 KB Output is correct
10 Correct 3 ms 14232 KB Output is correct
11 Correct 3 ms 14232 KB Output is correct
12 Correct 0 ms 14232 KB Output is correct
13 Correct 0 ms 14232 KB Output is correct
14 Correct 0 ms 14232 KB Output is correct
15 Correct 3 ms 14232 KB Output is correct
16 Correct 6 ms 14232 KB Output is correct
17 Correct 6 ms 14232 KB Output is correct
18 Correct 0 ms 14232 KB Output is correct
19 Correct 3 ms 14232 KB Output is correct
20 Correct 0 ms 14232 KB Output is correct
21 Correct 0 ms 14232 KB Output is correct
22 Execution timed out 2000 ms 14364 KB Execution timed out
23 Halted 0 ms 0 KB -