Submission #442836

#	Time	Username	Problem	Language	Result	Execution time	Memory
442836		ToniB	Hop (COCI21_hop)	C++14	110 / 110	48 ms	1424 KiB

Main

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <ext/pb_ds/assoc_container.hpp>
#include <bitset>
using namespace std;
using namespace __gnu_pbds;
#define FOR(i, x, n) for(int i = x; i < n; ++i)
#define REP(i, n) for(int i = 0; i < n; ++i)
#define TRACE(x) cerr << #x << " " << x << endl;
#define endl "\n"
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MOD = 1e9+7;
const int inf = 2147483647;
const int maxN = 1001;

ll x[maxN], n;
int ans[maxN];
bool bio[maxN];
vector<int> v[maxN], adj[maxN];
int indegree[maxN], ind[maxN], cind = 1;
void dfs(int node, int prev){
	bio[node] = 1;
	if(prev == -1){
		ans[node] = 0;
		REP(i, v[node].size()){
			dfs(v[node][i], node);
		}
	}
	else{
		ans[node] = max(ans[node], ans[prev]+1);
		indegree[node]--;
		if(indegree[node] == 0){
			REP(i, v[node].size()){
				dfs(v[node][i], node);
			}
		}
	}
}
void bfs(int node){
	if(bio[node]) return ;
	bio[node] = 1;
	REP(i, v[node].size()){
		bfs(v[node][i]);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
    cin >> n;
    REP(i, n) cin >> x[i];
    REP(i, n){
    	for(int j = i+1; j < n; ++j){
    		if(x[j] % x[i] == 0){
    			v[i].push_back(j);
    			adj[j].push_back(i);
    			adj[i].push_back(j);
    			indegree[j]++;
			}
		}
	}
	REP(i, n){
		if(!bio[i]){
			bfs(i);
			cind++;
		}
	}
	REP(i, n){
		bio[i] = 0;
	}
	REP(i, n){
		if(!bio[i] && indegree[i] == 0){
			dfs(i, -1);
		}
	}
	FOR(i, 1, n){
		REP(j, i){
			if(ind[i] != ind[j]){
				cout << 1 << " ";
			}
			else{
				if(ans[i]/16 != ans[j]/16){
					cout << 3 << " ";
				}
				else if(ans[i]/4 != ans[j]/4){
					cout << 2 << " ";
				}
				else{
					cout << 1 << " ";
				}
			}
		}
		cout << endl;
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:15:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define REP(i, n) for(int i = 0; i < n; ++i)
......
   35 |   REP(i, v[node].size()){
      |       ~~~~~~~~~~~~~~~~~             
Main.cpp:35:3: note: in expansion of macro 'REP'
   35 |   REP(i, v[node].size()){
      |   ^~~
Main.cpp:15:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define REP(i, n) for(int i = 0; i < n; ++i)
......
   43 |    REP(i, v[node].size()){
      |        ~~~~~~~~~~~~~~~~~            
Main.cpp:43:4: note: in expansion of macro 'REP'
   43 |    REP(i, v[node].size()){
      |    ^~~
Main.cpp: In function 'void bfs(int)':
Main.cpp:15:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define REP(i, n) for(int i = 0; i < n; ++i)
......
   52 |  REP(i, v[node].size()){
      |      ~~~~~~~~~~~~~~~~~              
Main.cpp:52:2: note: in expansion of macro 'REP'
   52 |  REP(i, v[node].size()){
      |  ^~~

• Subtask 1: 10 / 10
• Subtask 2: 100 / 100