제출 #306439

#제출 시각아이디문제언어결과실행 시간메모리
306439giorgikob슈퍼트리 잇기 (IOI20_supertrees)C++14
컴파일 에러
0 ms0 KiB
//#include "supertrees.h" #include <vector> #include <cassert> #include <cstdio> #include <cstdlib> #include <string> #include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; static int n; static std::vector<std::vector<int>> p; static std::vector<std::vector<int>> b; static bool called = false; static void check(bool cond, std::string message) { if (!cond) { printf("%s\n", message.c_str()); fclose(stdout); exit(0); } } void build(std::vector<std::vector<int>> _b) { check(!called, "build is called more than once"); called = true; check((int)_b.size() == n, "Invalid number of rows in b"); for (int i = 0; i < n; i++) { check((int)_b[i].size() == n, "Invalid number of columns in b"); } b = _b; } const int N = 1e3+5; vector<int>c[N]; int cnt = 0; int fix[N]; vector<int>chain; void dfs(int x,vector<vector<int>>&p){ fix[x] = 1; //cout << x << endl; c[cnt].pb(x); for(int i = 0; i < n; i++){ if(fix[i]) continue; if(p[x][i]){ dfs(i,p); } } } void dfs1(int x,vector<vector<int>>&p){ fix[x] = 1; //c[cnt].pb(x); chain.pb(x); //cout << x << endl; for(int i = 0; i < n; i++){ //cout << fix[i] << " "; if(fix[i]) continue; if(p[x][i] == 1){ dfs1(i,p); } } //cout << endl; } bool check(vector<int>&v){ for(int i = 0; i < v.size(); i++){ for(int j = 0; j < v.size(); j++){ if(p[v[i]][v[j]] == 2){ return 0; } } } return 1; } void cr(int x,int y,vector<vector<int>>&v){ v[x][y] = 1; v[y][x] = 1; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(p[i][j] == 3){ return 0; } } } //cout << "done 1" << endl; for(int i = 0; i < n; i++){ if(fix[i]) continue; cnt++;//cout << i << endl; dfs(i,p); } //cout << "done 2" << endl; for(int i = 0; i < n; i++) fix[i] = 0; for(int i = 1; i <= cnt; i++){ for(int j = 0; j < c[i].size(); j++){ for(int t = 0; t < c[i].size(); t++){ if(p[c[i][j]][c[i][t]] == 0){ return 0; } } } } //cout << cnt << endl; //cout << "done 3" << endl; //cout << cnt << endl; //vector<int>v; vector<vector<int>>answer(n,vector<int>(n,0)); vector<int>cyc; for(int i = 1; i <= cnt; i++){ //cout << c[i].size() << endl; for(int j = 0; j < c[i].size(); j++){ int x = c[i][j]; //cout << fix[x] << " " << x << " <<---"<< endl; if(fix[x]) continue; //cout << x << endl; chain.clear(); dfs1(x,p); //for(auto x : chain) cout << x << " "; cout << endl; if(check(chain) == 0){ return 0; } for(int t = 0; t+1 < chain.size(); t++){ int x = chain[t]; int y = chain[t+1]; cr(x,y,answer); } cyc.pb(chain[0]); } if(cyc.size() > 1) for(int i = 0; i < cyc.size(); i++){ int x = cyc[i]; int y = cyc[(i+1)%(int)cyc.size()]; cr(x,y,answer); } cyc.clear(); } //cout << "done 4" << endl; build(answer); return 1; } int main() { assert(scanf("%d", &n) == 1); p.resize(n); for (int i = 0; i < n; i++) { p[i].resize(n); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { assert(scanf("%d", &p[i][j]) == 1); } } fclose(stdin); int possible = construct(p); check(possible == 0 || possible == 1, "Invalid return value of construct"); if (possible == 1) { check(called, "construct returned 1 without calling build"); } else { check(!called, "construct called build but returned 0"); } printf("%d\n", possible); if (possible == 1) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j) { printf(" "); } printf("%d", b[i][j]); } printf("\n"); } } fclose(stdout); }

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'bool check(std::vector<int>&)':
supertrees.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
supertrees.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j = 0; j < v.size(); j++){
      |                        ~~^~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j = 0; j < c[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
supertrees.cpp:112:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for(int t = 0; t < c[i].size(); t++){
      |                            ~~^~~~~~~~~~~~~
supertrees.cpp:127:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int j = 0; j < c[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
supertrees.cpp:138:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |             for(int t = 0; t+1 < chain.size(); t++){
      |                            ~~~~^~~~~~~~~~~~~~
supertrees.cpp:146:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for(int i = 0; i < cyc.size(); i++){
      |                        ~~^~~~~~~~~~~~
/tmp/ccK8qVXM.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccXCcYuH.o:supertrees.cpp:(.text.startup+0x0): first defined here
/tmp/ccK8qVXM.o: In function `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)':
grader.cpp:(.text+0x1d0): multiple definition of `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
/tmp/ccXCcYuH.o:supertrees.cpp:(.text+0x320): first defined here
collect2: error: ld returned 1 exit status