oj.uz

답안 #1041703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1041703 2024-08-02T07:17:01 Z vjudge1 Izlet (COI19_izlet) C++17
0 / 100
 608 ms 44964 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 3000 + 10;
int c[N][N], n;

void subtask1()
{
  vector<pair<int, int> > G[n + 1];
  for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
      if(i != j)
	G[i].push_back({j, c[i][j] - 1});

  int dist[n + 1], par[n + 1];
  for(int i = 1; i <= n; i ++)
    dist[i] = n + 10, par[i] = -1;
  dist[1] = 0;
  deque<int> Q;
  Q.push_back(1);
  while(Q.size())
    {
      int v = Q.front();
      Q.pop_front();
      // cerr << v << endl;
      for(auto [u, w] : G[v])
	{
	  // cerr << "edge : " << u << ' ' << w << endl;
	  if(dist[v] + w < dist[u])
	    {
	      par[u] = v;
	      dist[u] = dist[v] + w;
	      if(w == 1) Q.push_back(u);
	      else Q.push_front(u);
	    }
	  else if(dist[v] + w == dist[u] && w == 0 && par[v] != u)
	    par[u] = v;
	}
    }

  for(int i = 1; i <= n; i ++)
    cout << dist[i] % 2 + 1 << ' ';
  cout << endl;

  for(int i = 2; i <= n; i++)
    cout << i << ' ' << par[i] << endl;
}

void subtask2()
{
}

int main()
{
  int t;
  cin >> t >> n;
  int mx = 0;
  for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
      cin >> c[i][j];
  
  if(t == 1)
    subtask1();
  else
    subtask2();
  return 0;
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:58:7: warning: unused variable 'mx' [-Wunused-variable]
   58 |   int mx = 0;
      |       ^~

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 2392 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 608 ms 44964 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 2392 KB Checker failed - contact admins or jury
2 Halted 0 ms 0 KB -