# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
16845 | gs14004 | 탐사 (KOI13_probe) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
int adj[45][45];
int n, k;
map<pi, int> mp;
int main(){
scanf("%d %d",&n,&k);
memset(adj,0x3f,sizeof(adj));
for(int i=0; i<=n; i++){
adj[i][i+1] = 1;
adj[i+1][i] = 0;
adj[i][i] = 0;
}
for(int i=0; i<k; i++){
int s, e, x;
scanf("%d %d %d",&s,&e,&x);
if(e - s + 1 < x){
putS("NONE");
return 0;
}
if(mp.find(pi(s, e)) != mp.end()){
if(mp[pi(s, e)] != x){
puts("NONE");
return 0;
}
else continue;
}
mp[pi(s, e)] = x;
adj[s-1][e] = x;
adj[e][s-1] = -x;
}
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
for(int k=0; k<=n; k++){
adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
}
}
}
for(int i=0; i<=n; i++){
if(adj[i][i] < 0){
puts("NONE");
return 0;
}
}
for(int i=1; i<=n; i++){
putchar(adj[0][i] - adj[0][i-1] ? '#' : '-');
}
}