Submission #1041703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041703		vjudge1	Izlet (COI19_izlet)	C++17	0 / 100	608 ms	44964 KiB

izlet

#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 (stderr)

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

• Subtask 1: 0 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57