Submission #532909

#	Time	Username	Problem	Language	Result	Execution time	Memory
532909		christinelynn	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, k;
int par[20005], par1[20005];
vector<pair<int, int> > adj1, adj0;
bool vis[20005];

vector<pair<int, pair<int, int> > > ans;

int find_par(int x) {
  if (par[x] == x) {
    return x;
  }
  return par[x] = find_par(par[x]);
}

int find_par1(int x) {
  if (par1[x] == x) {
    return x;
  }
  return par1[x] = find_par1(par1[x]);
}

void join(int a, int b) {
  par[find_par(a)] = par[find_par(b)];
}

void join1(int a, int b) {
  par1[find_par1(a)] = par1[find_par1(b)];
}


int main() {
  cin >> n >> m >> k;
  int sum = 0;
  for(int i =1 ;i <= n; i++) {
    par[i] = i;
    par1[i] = i;
  }
  for(int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    if (c == 0) {
      adj0.push_back({a, b});
      sum++;
    }
    else {
      adj1.push_back({a, b});
    }
  }
  
  if (sum < k) {
    cout << "no solution" << endl;
    return 0;
  }
  
  for(int i = 0; i < adj1.size(); i++) {
    //cout << adj1[i].first << " " << adj1[i].second << endl;
    join(adj1[i].first, adj1[i].second);
  }
  int cnt = 0;
  for(int i = 0; i < adj0.size(); i++) {
    //cout << find_par(adj0[i].first) << " " << find_par(adj0[i].second) << endl;
    if (find_par(adj0[i].first) != find_par(adj0[i].second)) {
      pair<int, pair<int, int> > next= make_pair(adj0[i].first, make_pair(adj0[i].second, 0));
      ans.push_back(next);
      join1(adj0[i].first, adj0[i].second);
      join(adj0[i].first, adj0[i].second);
      //cout << adj0[i].first << " " << adj0[i].second << endl;
      adj0[i] = make_pair(-1, -1);
      cnt++;
    }
  }
  
  
  for(int i = 0; i < adj0.size(); i++) {
    if (adj0[i].first != -1 && find_par1(adj0[i].first) != find_par1(adj0[i].second) && cnt < k) {
      pair<int, pair<int, int> > next= make_pair(adj0[i].first, make_pair(adj0[i].second, 0));
      ans.push_back(next);
      join1(adj0[i].first, adj0[i].second);
      //cout << adj0[i].first << " " << adj0[i].second << endl;
      adj0[i] = make_pair(-1, -1);
      cnt++;
    }
  }
  
  for(int i = 0; i < adj0.size(); i++) {
    if (adj0[i].first != -1 && find_par1(adj0[i].first) != find_par1(adj0[i].second) && cnt < k) {
      pair<int, pair<int, int> > next= make_pair(adj0[i].first, make_pair(adj0[i].second, 0));
      ans.push_back(next);
      join1(adj0[i].first, adj0[i].second);
      adj0[i] = make_pair(-1, -1);
      cnt++;
    }
    if (cnt >= k) {
      break;
    }
  }
  
  for(int i = 0; i < adj0.size(); i++) {
    if (cnt >= k) {
      break;
    }
    if (adj0[i].first != -1) {
      pair<int, pair<int, int> > next = make_pair(adj0[i].first, make_pair(adj0[i].second, 0));
      ans.push_back(next);
      join1(adj0[i].first, adj0[i].second);
      adj0[i] = make_pair(-1, -1);
      cnt++;
    }
  }
  
  for(int i = 0; i < adj1.size(); i++) {
    
    if (find_par1(adj1[i].first) != find_par1(adj1[i].second) ) {
      pair<int, pair<int, int> > next= make_pair(adj1[i].first, make_pair(adj1[i].second, 1));
      ans.push_back(next);
      join1(adj1[i].first, adj1[i].second);
    }
  }
  
  int tot = 0;
  for(int i = 1; i <= n; i++) {
    if (!vis[find_par1(i)]) {
      vis[find_par1(i)] = true;
      tot++;
    }
  }
  if (tot > 1) {
    cout << "no solution" << endl;
    return 0;
  }
  if (cnt != k) {
    cout << "no solution" << endl;
    return 0;
  }
  for(int i = 0; i < ans.size(); i++) {
    cout << ans[i].first << " " << ans[i].second.first << " " << ans[i].second.second << endl;
  }
}

Compilation message (stderr)

shoes.cpp: In function 'int main()':
shoes.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 0; i < adj1.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shoes.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i = 0; i < adj0.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shoes.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i = 0; i < adj0.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shoes.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i = 0; i < adj0.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shoes.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i = 0; i < adj0.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shoes.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int i = 0; i < adj1.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
shoes.cpp:138:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for(int i = 0; i < ans.size(); i++) {
      |                  ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccgQtVwz.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4je1Xz.o:shoes.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccgQtVwz.o: in function `main':
grader.cpp:(.text.startup+0x2a8): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status