oj.uz

Submission #847690

# Submission time Handle Problem Language Result Execution time Memory
847690 2023-09-10T07:08:22 Z vjudge1 KOVANICE (COI15_kovanice) C++17
10 / 100
 2000 ms 17232 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>> adjlistGBYKTR;
vector<int> par,sizev;
int finds(int a){
    if(a==par[a])return a;
    return par[a] = finds(par[a]);
}
void make_union(int a,int b){
    a=finds(a);
    b=finds(b);
    if(a!=b){
        if(sizev[a]<sizev[b]){
            swap(a,b);
        }
        par[b]=a;
        sizev[a]+=sizev[b];
    }
}

void PAL(int node,int deg){
    int p  = finds(node);
	for(int i=0;i<M;i++){
        if(finds(i)!=p)continue;
        type[i]=N-deg+1;
    }
}
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);
	adjlistGBYKTR = vector<vector<int>>(M,vector<int>(0));
    par = vector<int>(M);iota(par.begin(),par.end(),0);
    sizev = vector<int>(M,1);
	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=='='){
            make_union(i1,i2);
		}
		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 'bool DFS(int, int)':
kovanice.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<adjlistGBYKTR[node].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int j=0;j<s.size();j++){
      |               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 6 ms 548 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2040 ms 848 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 2049 ms 17232 KB Time limit exceeded
2 Halted 0 ms 0 KB -