oj.uz

답안 #442836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442836 2021-07-09T08:30:38 Z ToniB Hop (COCI21_hop) C++14
110 / 110
 48 ms 1424 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 368 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 368 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 47 ms 1412 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 41 ms 1272 KB Output is correct
12 Correct 48 ms 1324 KB Output is correct
13 Correct 42 ms 1308 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 42 ms 1348 KB Output is correct
16 Correct 43 ms 1348 KB Output is correct
17 Correct 44 ms 1340 KB Output is correct
18 Correct 43 ms 1416 KB Output is correct
19 Correct 45 ms 1424 KB Output is correct
20 Correct 45 ms 1348 KB Output is correct
21 Correct 42 ms 1364 KB Output is correct
22 Correct 42 ms 1372 KB Output is correct
23 Correct 46 ms 1340 KB Output is correct