oj.uz

Submission #846176

# Submission time Handle Problem Language Result Execution time Memory
846176 2023-09-07T12:10:45 Z vjudge1 KOVANICE (COI15_kovanice) C++17
50 / 100
 2000 ms 26588 KB 
#include <bits/stdc++.h>
#define min(x,y) (x>=y?y:x)
#define max(x,y) ((x)>=(y)?(x):(y))
#define xc3(x) (x*(x-1)*(x-2)/6)
#define xc2(x) (x*(x-1)/2)
#define GF G[node][i].first
#define s0b stk[0].begin()
#define s0e stk[0].end()
#define s1b stk[1].begin()
#define s1e stk[1].end()
using namespace std;
#define ll long long
#define ull unsigned long long
int N,M,V;
vector<int> type;
vector<vector<int>> adjlistGEQ,adjlistGBYKTR;
void PAL(int node,int deg){
	type[node]=N-deg+1;
	for(int i=0;i<adjlistGEQ[node].size();i++){
		if(type[adjlistGEQ[node][i]]==-1)
		PAL(adjlistGEQ[node][i],deg);
	}
}
bool DFS(int deg,int node){
	if(type[node]==deg)return true;
	if(deg==N){PAL(node,deg);return true;}
	for(int i=0;i<adjlistGBYKTR[node].size();i++){
		bool c = DFS(deg+1,adjlistGBYKTR[node][i]);
		if(c && type[node]==-1)PAL(node,deg);
	}
	return (type[node]==deg);
}

int main()
{
	cin>>N>>M>>V;
	type.assign(M,-1);
	vector<int> countt(M,0);
	adjlistGEQ = adjlistGBYKTR = vector<vector<int>>(M,vector<int>(0));
	for(int i=0;i<V;i++){
		string s;cin>>s;
		vector<string> a(2,"");int w=0;char t='c';
		for(int j=0;j<s.size();j++){
			if(s[j]=='=' || s[j]=='<'){	
				w++;
				t=s[j];
			}
			else a[w]+=s[j];
		}
		int i1=stoi(a[0]),i2=stoi(a[1]);i1--;i2--;
		if(t=='='){
			adjlistGEQ[i1].push_back(i2);
			adjlistGEQ[i2].push_back(i1); 
		}
		else{
			adjlistGBYKTR[i2].push_back(i1);
			countt[i1]++;
		}}
	for(int i=0;i<M;i++){
		if(countt[i]!=0)continue;
		DFS(1,i); // deg , node , parent
	}
	for(int i=0;i<M;i++){
		if(type[i]==-1)cout<<"?"<<endl;
		else{
			cout<<"K"<<type[i]<<endl;
		}
	}
	
}

Compilation message

kovanice.cpp: In function 'void PAL(int, int)':
kovanice.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<adjlistGEQ[node].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'bool DFS(int, int)':
kovanice.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<adjlistGBYKTR[node].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int j=0;j<s.size();j++){
      |               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 15144 KB Output is correct
2 Correct 279 ms 15184 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 1112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 26588 KB Time limit exceeded
2 Halted 0 ms 0 KB -